KMPアルゴリズムを使用して、文字列Bを部分文字列として含まない文字列Aの異なる部分文字列の数を見つけるにはどうすればよいですか？
別の問題にKMPアルゴリズムを使用しましたが、KMPでこの問題を解決する方法が見つかりませんでした。
前もって感謝します。
1 に答える
0
KMP は、かなり明確な頭脳が必要なカウントの問題では簡単なビットだと思います。KMP を使用すると、A の文字を順に調べて、B の出現を終了する A の文字を検出できます。これを使用して、B を含む A の部分文字列の数をカウントできます。
A の文字が B の出現を終了する場合、B を含むのに十分にさかのぼって開始するすべての部分文字列は、実際には B を含みます。B を含むには短すぎる部分文字列は、明らかにそうではありません。したがって、この場合、B を含むその文字で終わる A の部分文字列の数を数えることができます。
A の文字が B の出現を終了しない場合、B の前の出現を含むのに十分にさかのぼって始まるすべての部分文字列は、実際には B を含みます。したがって (B が最後に見られた場所を覚えていると仮定して) B を含むこの位置で終わる部分文字列の数をもう一度数えます。
したがって (各位置で終了する部分文字列の数を数えることは単純な算術演算を行うだけであるため、A の長さと B の長さの時間線形) で、B を含む A の部分文字列の数を数えることができます。 B を含まない部分文字列の数ですが、A の部分文字列の総数は A の長さの 2 次であるため、これも簡単です。
于 2012-08-18T04:55:57.020 に答える