アルファベットが5つの記号{a、b、c、d、＃}で構成され、特殊記号＃が任意の記号（それ自体を含む）と一致する場合、正確なパターンマッチングの問題を解決しようとしています。
たとえば、T = ab＃aca＃ab＃aおよびP = da＃acの場合、PはTの位置3から発生します。長さnのパターンPかどうかを判断するために、O（nlogn）時間アルゴリズムを見つけようとしています。 ＃記号がTとPで（おそらくO（n）回）発生すると仮定して、長さ2nのテキストTで発生します。
畳み込みでそれを解決する方法について何か提案はありますか？
述べたように、浮動小数点の精度を条件として、任意のアルファベットサイズについて問題を処理できると思います。n 文字のアルファベットの場合、テキスト文字を 1 の (複素) n 乗根にマップします。パターン文字の場合、# を 0 にマップし、通常の文字を対応するテキスト文字の乗法逆数にマップし、1 の n 乗根も同様にマップします。
次に、畳み込み定理を使用して、各ポイントで、そのポイントからのテキストとパターンの内積を計算します。テキストとパターンが一致する場合、積の各コンポーネントは r*r^-1 から 0 (ワイルド カードで) または 1 のいずれかになるため、一致した場合、結果は m になります。m は数値です。パターン内の非ワイルドカード文字。一致しない場合、内積のすべての成分が 1 になるわけではありません。これらの複素数を 2 次元ベクトルと考えると、これらのベクトルと 1 を表すベクトルとの内積は m 未満になるので、不一致は結果 m を引き起こすことができず、一致しているように見えます。
テキストをパターンの長さの数倍のバッファーに分割すると、その長さの FFT を合理的に効率的に使用できるため、複雑さは n log n ではありません。ここで、n はテキストの長さです。ただし、m はパターンの長さです。それにもかかわらず、単純な検索と比較しても、これが競争力のある方法であると信じる前に、ベンチマークのタイミングを確認する必要があります.
この実装が示すように、BNDM アルゴリズムはワイルドカード文字に対応でき、平均的な速度要件を満たします。ただし、最悪の場合の複雑さは O(nm) です。
ここで畳み込みが必要なのはなぜですか？