1 に答える
はい、アルゴリズムのような LCS を使用して最長の回文を見つけることは良い方法ではありません。参照された回答を注意深く読みませんでしたが、回答の次の行は完全に間違っています。
したがって、文字列内に含まれる最長の回文は、まさにこの文字列の最長の共通部分文字列であり、その逆です。
しかし、それを読んで反例があれば気にしないでください (99% 正しい)、これはよくある間違いですが、簡単な方法は次のとおりです。
barbapapa文字列 ( ) を次 のように書き留めます。次に#b#a#r#b#a#p#a#p#a#、この新しい文字列の各文字を左から右にトラバースし、その左右を調べて回文中心かどうかを確認します。このアルゴリズムは最悪の場合 O(n^2) であり、完全に正しく機能します。しかし、通常は O(n) で回文が見つかります (平均的なケースでこれを証明するのは確かに難しいです)。最悪のケースは、 のような長い回文が多すぎる文字列aaaaaa...aaaaです。
しかし、O(n) 時間かかるより良いアプローチがあり、このアルゴリズムのベースはManacherによるものです。関連するアルゴリズムは、参照された回答で見たものよりも複雑です。しかし、私が提供したのは Manacher アルゴリズムの基本的な考え方であり、アルゴリズムの巧妙な変更により、すべての左と右のチェックをスキップできます (サフィックス ツリーを使用するアルゴリズムもあります)。
PS: インターネットの制限により、Algo リンクが表示されませんでした。それが正しいかどうかはわかりません。
アルゴリズムを明確にするために、OP との議論を追加しました。
let test it with barbapapa-> #b#a#r#b#a#p#a#p#a#, start from first #
there is no left so it's center of palindrome with length 1.
Now "b",has # in left and # in right, but there isn't another left to match with right
so it's a center of palindrome with length 3.
let skip other parts to arrive to first "p":
first left and right is # second left and right is "a", third left and
right is # but forth left and right are not equal so it's center of palindrome
of length 7 #a#p#a# is palindrome but b#a#p#a#p is not
Now let see first "a" after first "p" you have, #a#p#a#p#a# as palindrome and this "a"
is center of this palindrome with length 11 if you calculate all other palindromes
length of all of them are smaller than 11
また、使用する#のは、長さが偶数の回文を考慮するためです。
新しく作成された文字列で回文の中心を見つけた後、関連する回文を見つけ（中心とその長さを知ることによって）、次に削除#して最大の回文を見つけます。