問題
要約
- 英小文字と'?'からなる2つの文字列S,Tが与えられる。
- Sの長さはTの長さより大きい。
- 2つの文字列がマッチするとは、両方の文字列の'?'を独立に好きな英小文字に置き換えることで、2つの文字列を一致させることができる場合を指す。
- x = 0, 1, ..., |T| (|T|はTの長さ) に対して、以下の操作を行う。
- Sの先頭x文字と末尾(|T|-x)文字を順番を保ったまま連結して、新しい文字列S'を作る。
- S'とTがマッチするかどうかを判定する。
- マッチする場合は'Yes'を、そうでない場合は'No'を出力する。
- この操作を|T|+1回（xの値ごとに1回）繰り返す。
- S, T: 与えられる2つの文字列
- |S|: Sの長さ
- |T|: Tの長さ
- x: 0から|T|までの整数
- S': Sから作られる新しい文字列（長さは|T|）
既存投稿一覧ページへのリンク
アプローチ1
文字列比較と差分管理を行う。
文字列Sから作られる新しい文字列S'とTの比較を、変化する部分のみを更新する。
解法手順1
-
入力文字列SとTを受け取る。
-
Tの長さ(t_len)を計算し、Sの末尾t_len文字(s_d)を取得する。
-
x = 0の場合の処理：
- s_dとTを比較し、異なる箇所をdiffリストに記録する。
- '?'は任意の文字にマッチするため、異なるとみなさない。
- diffの合計(sum_diff)が0ならマッチするため'Yes'を、そうでなければ'No'を出力する。
-
x >= 1の場合の処理：
- Sの先頭からt_len文字を順に処理する。
- 以前に異なっていた箇所が'?'または一致する文字になった場合、diffを更新し、sum_diffを減少させる。
- 以前に一致していた箇所が異なる文字になった場合、diffを更新し、sum_diffを増加させる。
- '?'は任意の文字にマッチするため、異なるとみなさない。
- 各ステップでsum_diffが0ならマッチするため'Yes'を、そうでなければ'No'を出力する。
-
手順4を繰り返し、全てのxに対する結果を出力する。
ACコード
ac.py
def io_func():
# 入力文字列SとTを受け取る
s = input()
t = input()
return s, t
def solve(s, t):
# Tの長さを計算
t_len = len(t)
# Sの末尾t_len文字を取得
s_d = s[-t_len:]
# x = 0のときの処理
diff = [False] * t_len # 差分を記録するリスト
sum_diff = 0 # 差分の合計
for i in range(t_len):
if s_d[i] == "?" or t[i] == "?":
continue # '?'は任意の文字にマッチするため、スキップ
if s_d[i] != t[i]:
diff[i] = True # 異なる箇所を記録
sum_diff += 1 # 差分の合計を増加
# x = 0の結果を出力
print("Yes" if sum_diff == 0 else "No")
# x >= 1の時の処理
for i in range(t_len):
if diff[i]:
if s[i] == "?" or s[i] == t[i]:
diff[i] = False # 以前に異なっていた箇所が一致
sum_diff -= 1 # 差分の合計を減少
else:
if s[i] == "?" or t[i] == "?":
print("Yes" if sum_diff == 0 else "No")
continue # '?'は任意の文字にマッチするため、次の文字へ
if s[i] != t[i]:
sum_diff += 1 # 新たな差分を発見
# 各ステップの結果を出力
print("Yes" if sum_diff == 0 else "No")
# メイン処理
s, t = io_func()
solve(s, t)
###
# s: 入力文字列S
# t: 入力文字列T
# t_len: 文字列Tの長さ
# s_d: 文字列Sの末尾t_len文字
# diff: 文字列SとTの差分を記録するリスト
# sum_diff: 差分の合計
# 1. io_func関数:
# - 標準入力から文字列SとTを読み込む
# - 読み込んだ文字列SとTを返す
# 2. solve関数:
# - 文字列SとTを受け取り、主な処理を行う
# - x = 0の場合の処理:
# - Sの末尾t_len文字とTを比較し、差分を記録
# - 差分の合計が0なら"Yes"、そうでなければ"No"を出力
# - x >= 1の場合の処理:
# - Sの先頭からt_len文字を順に処理
# - 差分の状態を更新し、各ステップで結果を出力
# 3. メイン処理:
# - io_func関数を呼び出して入力を受け取る
# - solve関数を呼び出して結果を出力する
ac.py
from abc import ABC, abstractmethod
# 単一責任の原則 (SRP): 入力処理を専門のクラスに分離
class InputHandler:
@staticmethod
def get_input():
return input(), input()
# 開放/閉鎖原則 (OCP): 抽象基底クラスを定義
class StringMatcher(ABC):
@abstractmethod
def is_match(self, char1, char2):
pass
# リスコフの置換原則 (LSP): 具象クラスは基底クラスと置換可能
class WildcardMatcher(StringMatcher):
def is_match(self, char1, char2):
return char1 == "?" or char2 == "?" or char1 == char2
# インターフェース分離の原則 (ISP): 小さなインターフェースに分割
class DiffCounter:
def __init__(self):
self.sum_diff = 0
def increment(self):
self.sum_diff += 1
def decrement(self):
self.sum_diff -= 1
def get_count(self):
return self.sum_diff
# 依存性逆転の原則 (DIP): 高レベルモジュールは低レベルモジュールに依存しない
class StringComparator:
def __init__(self, matcher: StringMatcher, diff_counter: DiffCounter):
self.matcher = matcher
self.diff_counter = diff_counter
def compare(self, s: str, t: str):
t_len = len(t)
s_d = s[-t_len:]
diff = [False] * t_len
# x = 0の処理
for i in range(t_len):
if not self.matcher.is_match(s_d[i], t[i]):
diff[i] = True
self.diff_counter.increment()
yield "Yes" if self.diff_counter.get_count() == 0 else "No"
# x >= 1の処理
for i in range(t_len):
if diff[i]:
if self.matcher.is_match(s[i], t[i]):
diff[i] = False
self.diff_counter.decrement()
elif not self.matcher.is_match(s[i], t[i]):
self.diff_counter.increment()
yield "Yes" if self.diff_counter.get_count() == 0 else "No"
def solve(s: str, t: str):
comparator = StringComparator(WildcardMatcher(), DiffCounter())
for result in comparator.compare(s, t):
print(result)
# メイン処理
if __name__ == "__main__":
s, t = InputHandler.get_input()
solve(s, t)