公式解説と同じように逆順に見て、以下のような問題を考えます。（下の文章は公式解説と同じです）

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

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

この新しい問題を、以下のような考え方で解きます。

ある\(i\)についてこの操作をした時に、新たに操作できるようになる位置がどこに増える可能性があるかを考えます。

• \({S_{i...i+M-1}}\)が#を含まないとき

  このときは、\({i}\)の右側と左側の両側に増える可能性があります。

• \({S_{i...i+M-1}}\)が##CDEのように「1つ以上の#+文字列」となっているとき

  このときは、\({i}\)の右側にのみ増える可能性があります。

• \({S_{i...i+M-1}}\)がABC##のように「文字列+1つ以上の#」となっているとき

  このときは、\({i}\)の左側にのみ増える可能性があります。

• \({S_{i...i+M-1}}\)が##CD#のように「1つ以上の#+文字列+1つ以上の#」となっているとき

  このときは、操作可能な位置は増えません。

以上の考察から、次のようなアルゴリズムを導けます。

1. \({i=0,1,...,N-M-1,N-M}\)の順に、\({i}\)について操作が可能であれば操作を行う。
2. \({i=N-M,N-M-1,...,1,0}\)の順に、\({i}\)について操作が可能であれば操作を行う。
3. \({S}\)の文字が全て#になったか確認する

時間計算量は\({O(NM)}\)です。

この解法はuruzunyaaさんに教えてもらいました。

実装例(C++):

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;

    auto replace = [&](int i) {
      if (ranges::equal(s.substr(i, m), t, [](char a, char b){
        return a==b || a=='#';
      })){
        for (int j=0; j<m; ++j) s[i+j]='#';
      }
    };
    for (int i=0; i<=n-m; ++i) replace(i);
    for (int i=n-m; i>=0; --i) replace(i);
    cout << (s == string(n, '#') ? "Yes" : "No") << endl;
}