ここに示されている「ドントケア」を使用したパターンマッチングのフィッシャー＆パターソンアルゴリズムを理解していると思います： http://u.cs.biu.ac.il/~amir/AlgII/fp-set1.html
ただし、私が理解したように、「ドントケア」の 1 次元マッチングを使用して、O((n^2)(logm)) 時間で 2 次元マッチングを解決することが可能です。そのためには、「ドント ケア」記号を各文字列の末尾などに追加し、これを 1 次元の問題に変換する必要があります。そこがよく分からない部分です。いくつか試してみましたが、それがどのように役立つかわかりません。
では、「ドントケア」を使用した 1D マッチングは、2D マッチングの解決にどのように役立つのでしょうか?
ありがとう。
編集：私はそれを理解したと思います。テキストを線形化する必要があります (行の連結)。パターンにも同じことが言えますが、各行の後に nm don't-care シンボルを追加する必要があります (パターンの最後の行を除く)。それでも、これには O((n^2)(log(m^2))) 時間がかかると思いますが、前述の時間は不可能だと思います。コメント?