私は最近、文字列の一致について勉強し、同様の問題を考えるようになりました。pをm文字の文字列、 tをn文字のテキストとする。問題は、次のようにpがtに出現するかどうかを調べることです: [0, n -1]の範囲にiが存在し、次のようになります。
p [ j ] = t [ i + j ] for j = 0, 1, ... , m - 1,
ここで、i + jはnを法として計算されます。例として、通常の文字列マッチングでは CDEFAB で ABCD は発生しませんが、上記の問題では CDEFAB で ABCD が発生することがわかります。この場合はi = 4 です。
パターンpがtで発生するかどうかを判断する線形時間アルゴリズムはありますか? そして、この問題は以前に治療されましたか？
前もって感謝します