1

私たちが使用した一般的な考え方は、文字列の残りの部分をチェックして比較する欲張りアルゴリズムを使用することでした。

このアイデアは機能しませんでした。一般的なアイデアは、おそらく何らかの接尾辞木またはKMPアルゴリズムを使用していますが、私が試したすべてが失敗します。

誰か助けてもらえますか？

PS：nは文字列の長さであり、文字列の文字はis [1..n]の間にあるため、T^nは接頭辞にnを掛けたものです。

4

1 に答える 1

3

ラビンカープアルゴリズムと同じようにローリングハッシュを使用します。最初にSを2倍にして、T^nがS*Sのプレフィックスであることを確認します。

次に、Tの長さを繰り返します。各長さについて、対数の複雑さでT ^ nのハッシュコードを計算できます（バイナリのべき乗とまったく同じです）。また、S * Sでの線形事前計算の後、一定時間内に各サブストリングのハッシュコードが見つかる場合があります（すべてのプレフィックスのハッシュを含む配列と、使用している素数の累乗を含む配列がもう1つ必要です）。ハッシュ用）。したがって、O（log（n））のT ^ n == SUBSTRING（S ^ 2、n * LENGTH_OG（T））の場合、各長さをチェックできます（ここでは、ハッシュを計算する時間を作る方法を少し考える必要があります各反復のt定数の）。したがって、提案された方法の全体的な複雑さは、O（LENGTH（S）* Log（LENGTH（S）））になります。

お役に立てれば。

編集：私は問題の線形解決策を見つけたと思います。あなたが言うように、それはKMPに基づいています。文字列の失敗関数を計算した後、その値を観察します。たとえば、次の場合です。

string s = "abcdababcdababcdababcdababc";

値は次のとおりです。

   a     b     c    d    a    b    a    b    c    d    a    b    a    b    c    d    a    b    a    b    c    d    a    b    a    b    c  
 -001  -001  -001  -001  000  001  000  001  002  003  004  005  006  007  008  009  010  011  012  013  014  015  016  017  018  019  020

最終的なインデックスで持っている値を見てください。Sの長さからそれを引いてからもう1つ引くと、繰り返される最短の部分文字列の長さが得られると思います。この例では、があります27 - 20 - 1 = 6。上記の場合、失敗関数が0から20までの値のシーケンスで終了する場合は、観察しやすくなります。ただし、実際には、20で終わる他の値がある場合は、0から20が再び有効な値になります。失敗関数は、いくつかの可能性をスキップするだけです。これが理にかなっていることを願っています。このアルゴリズムは線形です。

于 2012-04-23T12:20:27.753 に答える