これは、ここで少し前に議論された最長回文アルゴリズムに関する質問です。アルゴリズムを説明する引用されたブログ投稿は、次のように述べています。残念ながら、それらは証明を提供しておらず、次の中心が現在の回文の最長の回文固有接尾辞の中心である理由がよくわかりません。
誰かがそれを証明/説明できますか?
1 に答える
5
というわけで右に移動…
あなたの「現在の」回文が40文字だとしましょう。(たぶん、位置 100 を中心にしています。) より大きな位置を見つけようとしています。
(わかりました、900 文字の長さで、右に 50,000 文字のもっと大きなものがあるかもしれません。これにはまったく関係ありません。それは問題ありません。しかし、将来それについて説明します。今のところ、 40 より長い回文を探しながら、中心を右に移動します。意味がありますか?)
したがって、右に移動する必要があります。1 歩移動できます。しかし、どれも見逃すことなく、できるだけ遠くまで移動したいと考えています。
さて、右の次の文字にこれが含まれる場合...実際には、この 40 のグループの右端の文字を含める必要があります。すでにチェック済みなので、中央は 100 の後にある必要があり、40 よりも長くなるため、右側の文字#120を含める必要があります。)
では、どこまでさかのぼる必要があるのでしょうか。
さて、回文よりも(120 から) 戻ることはできません。真ん中の回文でなければ決して回文にはなりません。
3333333333333331110111
0 に「戻る」ことしかできません。0 の左側にある 1 (たとえば) は回文になることはありません。
とてもシンプルです。 右端の文字を含める必要があります (私たちのいずれかを含める場合)。また、できるだけ大きくする必要があります。また、回文は最初からしか始まらないため、回文にする必要があります (つまり、"真ん中から」) 回文で.
上の例では、左にある 1 または 0、または最も右にある 3 がこの宇宙で回文の中心になることはあり得ません。それらの周りには回文がないため、回文の中心になることは「決してない」可能性があります。
3 の真ん中にある 3 は、より大きな回文の中心にある可能性があることに注意してください....しかし、これがこれまでで最も長い回文であることを既に確認したことを忘れないでください (中心に基づいて、左から)。本当だ。
したがって、これよりも長い回文は、つまり、これよりも長い回文の次に考えられる開始点は 0 です。
言い換えれば、現在右側にある最大の回文の中心です。(つまり、短い回文である「111」ではなく、最も長い回文である「1110111」が右側にくっついています。)
実際、チェックする必要がある 2 つの可能性は、(A) "0" と (B) 最後から 2 番目のスポットの "1" です。もちろん、これら 2 つの可能性のうち、左から右に移動する必要があるため、(A) 「0」が実際に次にチェックするものです。
これらの 2 つ (問題の 0 と 1) は、「回文 1110111 が最後にくっついており、短い回文 111 が最後にくっついている」ということと同じであることを忘れないでください。
もちろん、1110111 の方が長いので、1110111 の中心は明らかに 111 の中心の左側にあります。
最も長い回文は右側にくっついていますが、もちろん中心は左側に最も近くなります。
うまくいけば、リンクされたブログでの議論の特定の部分が明確になることを願っています。私は意図的に多くの方法で自分自身を繰り返しました。ユングアルゴリズムの日です:)
繰り返しますが、私はマイケルが尋ねた非常に具体的な問題を具体的に明確にしようとしているだけであることに注意してください.
めちゃくちゃ混乱しますよね？
ところで、私はキャラクターのオンキャラクターとオフキャラクターのセンターの問題を単に無視しました - しかし、それはあなたが尋ねたことを理解することとは無関係です.
于 2010-12-09T15:31:26.857 に答える