0

重複の可能性:
回文を見つけるアルゴリズム

次のような文字列内のすべての回文を見つけるにはどうすればよいですか。

「AABBAATTAABB」

単一の文字列で回文を見つける方法を知っています。これらの文字列を " " 文字を削除してマージすると、回文を見つけることができます...しかし、そうすると、元の単語をどのように再構築すればよいでしょうか....

または、時間がかからない他のアプローチはありますか...手がかりはありますか..？

4

3 に答える 3

4

編集：私はあなたが求めているのはこれだと思います：文字列が与えられた場合、回文である可能性のあるすべての部分文字列をどのように決定しますか？

自明な回文である単一の文字から構築し、長さ2のすべての部分文字列を検討し、次に長さ3のすべての部分文字列を検討することができます。

幸いなことに、パリンドームには再帰的な関係があるため、最初と最後の文字を削除しても、パリンドロームが残っている必要があります。したがって、長さ4の文字列が回文（ABBAのように）である場合、最初と最後の文字が削除された部分文字列（'BB'）も回文である必要があります。

上で定義された再帰的関係はDPの最適なサブ問題の要件を満たすため、任意の文字列に対してこれを計算する動的計画法ソリューションを検討してください。

于 2013-01-18T20:07:21.487 に答える
0

問題は実際には、すべての部分文字列を見つけることになります。AA->a文字列内の各「単語」（AA、BB 、 AA BB->b、TTT など）を調べた後、各単語を 1 つの文字として見ることができるためTTT->t、例から新しい「縮小」文字列はabatab. のすべての部分文字列を検索しabatab、それぞれが回文であるかどうかを確認します。回文である場合は、マップ内の単語を検索して元の文字列を出力できます。例はaba -> AABBAAです。

単語がすべて同じ文字で構成されていない場合、問題はさらに興味深いものになります。あなたが持っていた場合AB BA。この場合AB、 とBAは回文ではありませんが、それらの連結は ですABBA。

于 2013-01-18T20:13:48.653 に答える
0

SauceMaster's answerは、回文問題を解決する方法を説明しています。

この質問に答えたいだけです。

私は単一の文字列で回文を見つける方法を知っています。これらの文字列を " " 文字を削除してマージすると、回文を見つけることができます...しかし、そうすると、どうすれば元の単語を再構築できますか?

最初に文字列のコピーを作成します。

于 2013-01-18T20:14:45.603 に答える