12

私は、CormemのIntroduction to Algorithms 3rd edition（pg 405）から動的計画問題を解決しようとしています。

回文は、同じ前方と後方を読み取るいくつかのアルファベット上の空でない文字列です。回文の例は、すべて長さ1 civic、、、、racecarおよびaibohphobia （回文の恐怖）の文字列です。

与えられた入力文字列のサブシーケンスである最長の回文を見つけるための効率的なアルゴリズムを提供します。たとえば、入力が与えられた場合 character、アルゴリズムはを返す必要がありますcarac。

ええと、私はそれを2つの方法で解決することができました：

最初の解決策：

文字列の最長パリンドロームサブシーケンス（LPS）は、それ自体の最長共通サブシーケンスとその逆です。（シーケンスの最長増加部分列を求める別の関連する質問を解決した後、このソリューションを構築しました）。これは単なるLCSバリアントであるため、O（n²）時間とO（n²）メモリも必要です。

2番目の解決策：

2番目の解決策はもう少し複雑ですが、一般的なLCSテンプレートにも準拠しています。それは次の再発から来ています：

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

lpsの長さを計算するための擬似コードは次のとおりです。

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

lpを効果的に構築したい場合は、それでもO（n²）の時間とメモリが必要です（テーブル上のすべてのセルが必要になるため）。LCSのようなメモリの少ないアプローチ（LISはO（n）メモリで解決可能）以外のアプローチで解決できるLISなどの関連する問題を分析して、O（n）メモリで解決できるかどうか疑問に思いました。それも。

LISは、候補のサブシーケンスをリンクすることでこの限界を達成しますが、パリンドロームでは、ここで重要なのはサブシーケンスの前の要素ではなく、最初の要素であるため、より困難です。誰かがそれを行うことが可能かどうか知っていますか、または以前のソリューションはメモリが最適ですか？

4

2 に答える 2

6

これは非常にメモリ効率の良いバージョンです。しかし、私はそれが常に O(n)記憶であることを示していません。（前処理ステップを使用すると、最悪の場合ですが、CPUよりも優れている可能性があります。）O(n2)O(n2)

左端の位置から開始します。各位置について、長さ1、2、3などの反映されたサブシーケンスを生成できる最も遠いポイントのテーブルを追跡します（ポイントの左側のサブシーケンスが右側に反映されることを意味します）。反映された各サブシーケンスには、サブシーケンスの次の部分へのポインタが格納されます。

正しく作業するときに、文字列のRHSから現在の要素の出現箇所の位置まで検索し、それらの一致を使用して以前の境界を改善しようとします。終了したら、ミラーリングされた最長のサブシーケンスを確認し、最高の回文を簡単に作成できます。

これを考えてみましょうcharacter。

  1. (0, 11)最高の回文は文字「c」で始まり、ミラーリングされたサブシーケンスは、文字列の端から外れたペアで到達します。
  2. 次に、位置1の「c」について考えます。フォームでミラーリングされた最適なサブシーケンスは次のよう(length, end, start)になります[(0, 11, 0), (1, 6, 1)]。（実際に回文を見つけるために生成する必要のあるリンクリストは省略します。
  3. 次にh、位置2について考えます。境界を改善しません[(0, 11, 0), (1, 6, 1)]。
  4. 次にa、位置3について考えます。境界をに改善します[(0, 11, 0), (1, 6, 1), (2, 5, 3)]。
  5. 次にr、位置4について考えます。境界をに改善します[(0, 11, 0), (1, 10, 4), (2, 5, 3)]。（これは、リンクリストが役立つ場所です。

リストの残りの部分を処理しても、その境界のセットは改善されません。

したがって、ミラーリングされた最長のリストの長さは2になります。そして、リンクリストをたどります（この説明では記録していませんが、それを見つけましたac。そのリストの終わりは位置にあるので、(5, 3)反転できます。リスト、文字を挿入4し、リストを追加して取得しますcarac。

一般に、必要となる最大メモリは、ミラーリングされた最大サブシーケンスのすべての長さに加えて、前記サブシーケンスのリンクリストを格納するためのメモリを格納することです。通常、これは非常に少量のメモリになります。

従来のメモリとCPUのトレードオフでは、リストを一度に前処理して、特定のシーケンス要素が表示される配列のサイズのハッシュO(n)を生成できます。O(n)これにより、文字列全体を考慮する必要なしに、「このペアリングでミラー化されたサブシーケンスを改善する」をスキャンできます。これは、通常、長い文字列のCPUを大幅に節約するはずです。

于 2011-05-26T02:19:15.133 に答える
3

@Luiz Rodrigoの質問の最初の解決策は間違っています。文字列の最長共通部分列（LCS）とその逆は、必ずしも回文ではありません。

例：文字列CBACBの場合、CABは文字列とその逆のLCSであり、明らかに回文ではありません。ただし、それを機能させる方法はあります。文字列のLCSとその逆が作成されたら、左半分（奇数の長さの文字列の場合は中文字を含む）を取り、右を逆の左半分（文字列の長さが奇数の場合は中文字を含まない）で補完します。 ）。それは明らかに回文であり、それが文字列のサブシーケンスになることは簡単に証明できます。

上記のLCSの場合、この方法で作成された回文はCACになります。

于 2011-06-06T14:50:44.970 に答える