以下、文字列 \(S\) の \(i\) 文字目 (0-indexed) を \(S_i\) と表記します。

操作を逆順に見ると、以下のような問題に変わります。

\(S\) に対して以下の操作を繰り返し行うことで、\(S\) の文字を全て # にすることができるか判定せよ。

• 全ての \(j\ (0 \leq j < M)\) に対して「\(S_{i+j}=T_j\) または \(S_{i+j}= \)# 」を満たすような \(i\ (0 \leq i < N-M+1)\) を \(1\) つ選び、\(S_i, S_{i+1}, \dots, S_{i+M-1}\) を全て # で置き換える。

全ての \(j\ (0 \leq j <M)\) に対して「\(S_{i+j}=T_j\) または \(S_{i+j}= \)# 」を満たすような \(i\) のことを「良い \(i\)」と呼びます。また、\(S_i, S_{i+1}, \dots, S_{i+M-1}\) を全て # で置き換えることを単に「\(i\) に対して操作を行う」と呼びます。

この新しい問題は、以下のような簡単な貪欲法によって解くことができます。

1. 良い \(i\) であって、まだ操作を行ったことがないような \(i\) を探す。
2. そのような \(i\) が存在するならば、その \(i\) に対して操作を行い、1. に戻る。存在しないならば、今 \(S\) の文字が全て # になっているかどうかで答えを判定する。

証明は、同じ \(i\) に対して \(2\) 回以上操作を行う必要がないことと、良い \(i\) が存在するならば今すぐその \(i\) に対して操作をしても損しないことから従います。

しかし、良い \(i\) を探すパートに毎回 \(O(N)\) かけていては間に合いません。そこで、以下のようなアルゴリズムを用います。

1. キュー \(Q\) を用意し、初期状態における良い \(i\) を全て \(Q\) に入れる。
2. \(Q\) が空でない限り、以下を繰り返す。
   • \(Q\) から要素を \(1\) つ取り出して \(i'\) とする。\(i'\) に対して操作をしたのち、この操作によって新たに良い \(i\) となった \(i\) を全て \(Q\) に入れる。
3. \(S\) の文字が全て # になったか確認する。

キューから要素を取り出す回数は高々 \(N\) 回であり、\(i'\) への操作によって新たに良い \(i\) となりうるのは \(i'-M+1, i'-M+2, \dots, i'+M-1\) の \(O(M)\) 個であることから、\(O(NM^2)\) や \(O(NM)\) の計算量でこの問題を解くことができます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    vector<bool> used(n - m + 1);
    queue<int> q;
    auto check = [&](int i) {
        if (used[i]) return;
        bool ok = true;
        for (int j = 0; j < m; j++) {
            ok &= (s[i + j] == '#' or s[i + j] == t[j]);
        }
        if (ok) {
            used[i] = true;
            q.push(i);
        }
    };
    for (int i = 0; i < n - m + 1; i++) check(i);
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j = 0; j < m; j++) s[i + j] = '#';
        for (int j = max(i - m + 1, 0); j <= min(i + m - 1, n - m); j++) {
            check(j);
        }
    }
    cout << (s == string(n, '#') ? "Yes" : "No") << endl;
}