-2

アルゴリズムの問​​題が 1 つ見つかりました。私はその問題を解決しましたが、それを最適化したいです。ここで同じ問題を尋ねます。

問題

1 つの文字列が指定され、その文字列の長さはN <= 10000000です。その文字列のすべての文字は'a' から 'z'です。次に、末尾に文字を追加して、指定された文字列から作成できる最小の回文を計算する必要があります。

例

与えられた文字列 = 'abab'

出力 = 'アババ'

理由: 文字列には、文字列の先頭と末尾の両方から始まる文字列ababaが含まれておりabab、両端に余分な文字が 1 つだけあります。

編集済み

文字列 = 'abbcd' 出力 = 'abbcdcbba'

私の試み

この問題は O(N^2) の複雑さで解決できます。

私の質問

この問題を O(N^2) 時間以内に解決できますか? 、はいの場合、アルゴリズムは何ですか? （私にヒントをください）

4

2 に答える 2

4

回文では、文字列の中央までの距離が等しいすべての文字のペアが等しいことに注意してください。

これは、次のアルゴリズムを示唆しています。

最大の回文接尾辞を見つけて、この回文接尾辞の左側に部分文字列の反転を追加します。これにより、文字列の末尾に文字を追加することで得られる最短の回文が得られます。

これのブルート実装はO(n^2). O(n)2 つのローリング ハッシュを使用して、接尾辞が回文であるかどうかをテストできますO(1)。

これらのハッシュがどのように機能するかの概要は次のとおりです。

hForward(suff)  = suff[0] * p^0 + suff[1] * p^1 + ... + suff[k] * p^k
hBackward(suff) = suff[k] * p^0 + suff[k-1] * p^1 + ... + suff[0] * p^k

When adding a new character to the suffix:
Note that this is added to the beginning, since we should iterate the suffixes
from right to left.
hForward(c + suff) = c * p^0 + p * hForward(suff)
hBackward(c + suff) = hBackward(suff) + c * p^(k + 1)

おそらくどこpに（小さい）素数があるべきであり、すべての計算を別の（大きい）素数で行う必要があります。効率を維持するために、べき乗をインクリメンタルに計算し、べき乗アルゴリズムを使用しないでください。偽陽性を回避するために、より多くのハッシュを使用できます。

混乱していなければ、 KMPアルゴリズムを使用した解決策もありますが、私はもうよく知りません。

于 2013-08-03T15:20:16.890 に答える
0

簡単な θ(n) アプローチ (n 文字の入力文字列 S の場合) は、 S のサフィックス ツリーT を θ(n) 時間で構築することです。R=reverse(S)とする。時間 O(n) で、T を使用して、S の接尾辞の中から R の最長一致を見つけます。最長一致が m 文字であるとします。つまり、R の最初の m 文字は S の最後の m と一致し、m は最大です。P を R の最後の nm 文字、または S の最初の nm の反転とする。望ましい結果は S + P である。

于 2013-08-03T18:27:28.373 に答える