1

与えられたintシーケンスについて、ダブルパリンドロームの数を確認します。ここで、ダブルパリンドロームとは、2つの同じパリンドロームのシーケンスを意味します。したがって、たとえば：

1 0 1 1 0 1には、休憩なしで2回出現する回文として101があります。

1 0 1 5 1 01には101がありますが、分離されています

（これらのシーケンスの他のパリンドロームは別として）

問題の例のテストデータは次のとおりです。

3

12 0 1 1 0 0 1 1 0 0 1 1 0

12 1 0 1 0 1 0 1 0 1 0 1 0

6 3 3 3 3 3 3

答えを持って

8 0 9

マナチャーは物乞いをしているのは明らかですが、次に何をすべきかわかりません。どんなアイデアでもありがたいです。複雑さはn^2未満であると思います。

編集：intはここではアルファベットの単一要素として扱われます

4

2 に答える 2

0

私は2つのコレクションから始めます：

  • 「成長する」シーケンスのコレクション
  • 「縮小」シーケンスのコレクション

アルゴリズムは次のように機能します。

  • 最初は両方のコレクションが空です
  • ベクトルの値を1つずつ処理し、値Vを見ていると仮定します。
  • すべての「成長する」シーケンスをループします
    • 成長するシーケンスの最後の値がVに等しい場合は、成長するシーケンスを縮小するシーケンスのコレクションにコピーし、新しい縮小するシーケンスの最後からVを削除します。
    • 成長シーケンスの最後の1つがVに等しい場合は、成長シーケンスを縮小シーケンスのコレクションにコピーし、縮小シーケンスから最後の2つの要素（Vと最後の要素）を削除します。
  • すべての「縮小」シーケンスをループします
    • 縮小シーケンスの最後の値がVに等しい場合は、縮小シーケンスから削除します。縮小シーケンスが空になると、回文が見つかりました。
    • 縮小シーケンスの最後の値がVと等しくない場合は、この縮小シーケンスを削除します
  • 最後に、Vのみで構成される新しい成長シーケンスを作成します

実際、成長するシーケンスは一度回文になる可能性のあるシーケンスですが、縮小するシーケンスは「部分的に」回文です。

于 2010-06-09T20:30:32.347 に答える
0

すべての回文を見つけるためのアルゴリズム（ところで、これはかなり素晴らしいです）をすでに知っているので、あなたがする必要があるのは次のことだけです。「ダブルパリンドローム」もパリンドロームであることに注意してください：
reverse（PP）= reverse（P）reverse（P）=PP。

(a,b)したがって、あなたが見つけるすべての回文の中で（私は位置から位置へ(a,b)の回文を意味します）、、、、およびがすべて回文であるようなものを見つける必要があります。同様に、見つけた回文ごとに、を設定し、とが両方とも回文であるかどうかを確認する必要があります。ab(i,j,k)(i,j)(j,k)(i,k)j-i=k-j(i,j)k = 2j-i(k,j)(i,k)

最初のステップで全部でM回文が返される場合、これにはO（M）時間がかかります（回文が存在するかどうかをチェックするようにそれらを保存したと仮定すると、O（1））。したがって、最悪の場合はO（n 2 ）になります。最悪の場合、これが最適であると思います（すべて1の文字列を検討してください）。

于 2010-07-17T04:45:16.840 に答える