【競技プログラミング】AtCoder Beginner Contest 287_D問題

# 問題
https://atcoder.jp/contests/abc287/tasks/abc287_d

## 要約
1. 英小文字と'?'からなる2つの文字列S,Tが与えられる。
2. Sの長さはTの長さより大きい。
3. 2つの文字列がマッチするとは、両方の文字列の'?'を独立に好きな英小文字に置き換えることで、2つの文字列を一致させることができる場合を指す。
4. x = 0, 1, ..., |T| (|T|はTの長さ) に対して、以下の操作を行う。
   - Sの先頭x文字と末尾(|T|-x)文字を順番を保ったまま連結して、新しい文字列S'を作る。
   - S'とTがマッチするかどうかを判定する。
   - マッチする場合は'Yes'を、そうでない場合は'No'を出力する。
5. この操作を|T|+1回（xの値ごとに1回）繰り返す。

- S, T: 与えられる2つの文字列
- |S|: Sの長さ
- |T|: Tの長さ
- x: 0から|T|までの整数
- S': Sから作られる新しい文字列（長さは|T|）

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# アプローチ1
文字列比較と差分管理を行う。
文字列Sから作られる新しい文字列S'とTの比較を、変化する部分のみを更新する。

# 解法手順1

1. 入力文字列SとTを受け取る。

2. Tの長さ(t_len)を計算し、Sの末尾t_len文字(s_d)を取得する。

3. x = 0の場合の処理：
   - s_dとTを比較し、異なる箇所をdiffリストに記録する。
   - '?'は任意の文字にマッチするため、異なるとみなさない。
   - diffの合計(sum_diff)が0ならマッチするため'Yes'を、そうでなければ'No'を出力する。

4. x >= 1の場合の処理：
   - Sの先頭からt_len文字を順に処理する。
   - 以前に異なっていた箇所が'?'または一致する文字になった場合、diffを更新し、sum_diffを減少させる。
   - 以前に一致していた箇所が異なる文字になった場合、diffを更新し、sum_diffを増加させる。
   - '?'は任意の文字にマッチするため、異なるとみなさない。
   - 各ステップでsum_diffが0ならマッチするため'Yes'を、そうでなければ'No'を出力する。

5. 手順4を繰り返し、全てのxに対する結果を出力する。


# ACコード
```python: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)
```