8

回転した回文は、「1234321」、「3432112」のようになります。素朴な方法では、文字列をさまざまな断片に切り取り、それらを連結して、文字列が回文かどうかを確認します。n 個のカットがあり、カットごとに文字列が回文かどうかを確認するには O(n) が必要なので、これには O(n^2) が必要です。これよりも良い解決策があるかどうか疑問に思っています。そうですか、アドバイスお願いします。

ありがとう！

4

5 に答える 5

6

このウィキペディアの記事によると、時間O（n）の長さnの各文字列Sについて、次のように同じサイズの配列Aを計算することができます。

長さiのSの接頭辞が回文である場合、A [i]==1。

http://en.wikipedia.org/wiki/Longest_palindromic_substring

アルゴリズムは次の場所で見つけることができるはずです。

Manacher、Glenn（1975）、「文字列の最小の初期回文を見つけるための新しい線形時間「オンライン」アルゴリズム」

言い換えると、文字列のどのプレフィックスが線形時間で回文であるかを確認できます。この結果を使用して、提案された問題を解決します。

各（非回転）回文Sは、次の形式S = psxs ^ Rp^Rを持ちます。

「x」が回文の中心（空の文字列または1文字の文字列）である場合、「p」と「s」は（おそらく空の）文字列であり、「s^R」は「s」文字列が逆になっていることを意味します。

この文字列から作成された各回転回文には、次の2つの形式のいずれかがあります（一部のpの場合）。

  1. sxs ^ Rp ^ Rp
  2. p ^ Rpsxs ^ R

これは、パリンドロームの中央の前または後にサブストリングをカットして、もう一方の端に貼り付けることができるためです。

部分文字列「p^Rp」と「sxs^R」はどちらも回文であり、Sが奇数の場合、一方は偶数の長さで、もう一方は奇数の長さです。

ウィキペディアのリンクに記載されているアルゴリズムを使用して、2つの配列AとBを作成できます。配列Aは、どのプレフィックスが回文で、Bがサフィックスであるかを確認することで作成されます。次に、接頭辞または接尾辞のいずれかが偶数の長さになるように、A [i] == B [i]==1となる値iを検索します。提案された文字列が回転した回文であり、偶数部分が「p ^ Rp」サブ文字列である場合、このようなインデックスが見つかります。したがって、この文字列の半分を文字列のもう一方の端に移動することで、元の回文を簡単に復元できます。

rksによる解決策に対する1つの注意点として、この解決策は機能しません。文字列S = 1121の場合、Sの長さ以上の長さの回文を持つ文字列11211121が作成されますが、回転した回文ではありません。Sの長さに等しい長さの回文が存在するかどうかをチェックするようにソリューションを変更すると、それは機能しますが、最長の部分文字列を検索するアルゴリズムを変更する方法がわかりません。固定長のサブストリング（len（S））を検索します。（私はStackoverflowを初めて使用し、そうするのに十分な評判がないため、ソリューションの下でコメントとしてこれを書きませんでした）

2番目のコメント-Manacherのアルゴリズムを含めないことをお詫びします。誰かがアルゴリズムのアイデアまたは何らかの実装へのリンクを持っている場合は、コメントに含めてください。

于 2012-09-05T18:28:16.210 に答える
2

文字列をそれ自体に連結してから、新しい文字列で古典的な回文の調査を行います。元の弦の長さ以上の長さの回文を見つけた場合は、弦が回転した回文であることがわかります。

あなたの例では、最初の文字列よりも長い、を34321123432112見つけて調査を行うので、回転した回文になります。21123432112

編集：Richard Stefanecが指摘したように、私のアルゴリズムは失敗します。彼は、長さのテストを。だけ1121変更することを提案しました。>==

EDIT2：与えられたサイズの回文を見つけることは明らかに簡単ではないことに注意する必要があります。詳細については、RichardStefanecの投稿の下にあるディスカッションをお読みください。

于 2012-09-05T16:56:56.823 に答える
0

従来のアルゴリズムのみを使用した簡単な解決策を 1 つ提案したいと思います。難しい問題は解決しませんが、タスクには十分なはずです。これは他の 2 つの提案された解決策といくらか似ていますが、どれも私が注意深く読むには十分に簡潔ではないようです。

最初のステップ:他のすべての提案されたソリューションと同様に、文字列をそれ自体 ( abvc- > ) に連結します。abvcabvc

2 番目のステップ:新しく取得した文字列とその逆に対して、Rabin-Karp 事前計算(ローリング ハッシュを使用) を実行します。

3 番目のステップ:文字列の長さを指定しnます。Rabin-Karp 事前計算を使用して、2 倍の文字列の部分文字列が定数時間で回文であるかどうかiをチェックするインデックスごとに (基本的に、順方向と逆方向の部分文字列で得られた値は等しいはずです)。0...n-1[i, i + n - 1]

結論: 3 番目のステップで回文が見つかった場合、文字列は回文で回転されます。そうでない場合は、そうではありません。

PS: Rabin Karp はハッシュを使用しており、文字列が一致しない場合でも衝突が発生する可能性があります。したがって、ハッシュチェックによって同等性が引き起こされた場合、ブルートフォースチェックで同等性を検証することをお勧めします。それでも、Rabin Karp で使用されているハッシュ関数が優れていれば、ソリューションの償却速度は維持されるはずですO(n)。

于 2012-09-06T10:36:26.980 に答える
-1

元のパターンの最後に同じパターンを追加できます。たとえば、パターンが 1234321 の場合、同じパターンを 12343211234321 の末尾に追加できます。これを行った後、KMP またはその他の部分文字列一致アルゴリズムを使用して、必要な文字列を見つけることができます。一致する場合は、ture を返します。

于 2015-01-03T12:26:42.090 に答える