5

文字列の中で最も長い回文部分列を見つけたいです。どこでも、サブシーケンスの長さを見つけるアルゴリズムを見つけ、アルゴを拡張してサブシーケンスを返すことができるというステートメントを見つけましたが、その方法はどこにも見つかりませんでした。シーケンスを取得する方法を誰かが説明できますか?

4

6 に答える 6

8

geeksforgeeksのリンクLongest Palindromic Subsequenceについて言及したので、結果を出力するようにソリューションを変更しました。パリンドローム部分列がどのように由来するかを格納するには、1 つの補助的な 2 次元配列が必要だと思います。これにより、最終的に補助配列を介して結果を得ることができます。以下のコードでロジックを確認できます。

#include<iostream>
#include<cstring>

using namespace std;

// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }

// Returns the length of the longest palindromic subsequence in seq
int lps(char *str,char *result)
{
   int n = strlen(str);
   int i, j, cl;
   int L[n][n];  // Create a table to store results of subproblems

   int Way[n][n];// Store how the palindrome come from.


   // Strings of length 1 are palindrome of lentgh 1
   for (i = 0; i < n; i++)
   {
       L[i][i] = 1;
       Way[i][i]=0;
   }


    // Build the table. Note that the lower diagonal values of table are
    // useless and not filled in the process. The values are filled in a
    // manner similar to Matrix Chain Multiplication DP solution (See
    // http://www.geeksforgeeks.org/archives/15553). cl is length of
    // substring
    for (cl=2; cl<=n; cl++)
    {
        for (i=0; i<n-cl+1; i++)
        {
            j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
            {
                   L[i][j] = 2;
                   Way[i][j]=0;     
            }

            else if (str[i] == str[j])
            {
                  L[i][j] = L[i+1][j-1] + 2;
                  Way[i][j]=0;
            }

            else
            {
                if(L[i][j-1]>L[i+1][j])
                {
                   L[i][j]=L[i][j-1];
                   Way[i][j]=1;                    
                }
                else
                {
                    L[i][j]=L[i+1][j];
                    Way[i][j]=2;  
                }

            }

        }
    }

    int index=0;
    int s=0,e=n-1;

    while(s<=e)
    {
         if(Way[s][e]==0)
         {
             result[index++]=str[s];
             s+=1;
             e-=1;

         }
         else if(Way[s][e]==1)e-=1;
         else if(Way[s][e]==2)s+=1;     
    }

    int endIndex=(L[0][n-1]%2)?index-1:index;

    for(int k=0;k<endIndex;++k)result[L[0][n-1]-1-k]=result[k];

    result[index+endIndex]='\0';


    return L[0][n-1];
}

/* Driver program to test above functions */
int main()
{
    char seq[] = "GEEKSFORGEEKS";
    char result[20];
    cout<<"The lnegth of the LPS is "<<lps(seq,result)<<":"<<endl;
    cout<<result<<endl;
    getchar();
    return 0;
}

それが役に立てば幸い！

以下に説明を示します。

X[0..n-1] を長さ n の入力シーケンスとし、L(0, n-1) を X[0..n-1] の最長回文サブシーケンスの長さとします。

全部で5ケースあります。

1) すべての単一文字は、長さ 1 の回文です。L(i, i) = 1 は、指定されたシーケンス内のすべてのインデックス i に対してです。

2) キャラクターは 2 人だけで、どちらも同じです。L(i, j) = 2.

3)2文字以上で、最初と最後の文字が同じ L(i, j) = L(i + 1, j - 1) + 2

4)最初と最後の文字が異なり、L(i + 1, j)< L(i, j - 1)。L(i, j) = L(i, j - 1)。

5)最初と最後の文字が異なり、L(i + 1, j)>=L(i, j - 1)。L(i, j) = L(i + 1, j)。

ケース 1、2、および 3 でのみ、文字 X[i] が最終結果に含まれていることがわかります。2 次元の補助配列を使用して、回文サブシーケンスがどのように由来するかを表しました。ケース 1、2、3 の場合は値 0。ケース 4 の値は 1。ケース 5 の値 2。

補助アレイウェイ付き。以下のように結果を取得できます。

Let two variables s=0 and e=n-1.
While s<=e
Loop
    If Way[s][e]==0 Then X[s] should be included in the result and we store it in our result array.
    Else if Way[s][e]==1 Then X[s] should not be include in the result and update e=e-1 (because our result comes from case 4).
    Else if Way[s][e]==2 Then X[s] should not be include in the result and update s=s+1 (because our result comes from case 5).

ループは、s>e のときに終了する必要があります。このようにして、結果の半分を得ることができ、それを簡単に拡張して全体の結果を得ることができます。

于 2012-10-15T16:49:26.857 に答える
4

各セルの動的プログラミング テーブルにバックポインターと値を保持します。次に、テーブルの最後からトレースバックをたどって、サブシーケンスを再構築します。

于 2012-10-15T10:07:39.420 に答える
1

トリックは次のように機能します。

2 番目の文字列の定義により、両方の文字列の LCS も最長の回文であることに注意してください。

于 2012-10-15T11:57:51.070 に答える
1

以下のソリューションは非常に簡単で、他のマトリックスを追加で使用する必要はありません。ここでは、最長のパリンドローム部分シーケンスを生成するためにパスをさかのぼるだけです。

int lps(char *str)
{
   int n = strlen(str);
   int i, j, cl;
   int L[n][n];  
   for (i = 0; i < n; i++)
      L[i][i] = 1;
    for (cl=2; cl<=n; cl++)
    {
        for (i=0; i<n-cl+1; i++)
        {
            j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
               L[i][j] = 2;
            else if (str[i] == str[j])
               L[i][j] = L[i+1][j-1] + 2;
            else
               L[i][j] = max(L[i][j-1], L[i+1][j]);
        }
    }
    cout<<L[0][n-1]<<endl;
    i = 0,j = n-1;
    vector<char> result;
    while(i<=j)
    {
        if(str[i]==str[j])
        {
            result.push_back(str[i]);
            i++,j--;
        }
        else if(L[i][j-1]>L[i+1][j])
        {
            j--;
        }
        else
        {
            i++;
        }
    }
    if(L[0][n-1]%2==0)
    {
        for(auto i = result.begin();i!=result.end();i++)
            cout<<*i;
        reverse(result.begin(),result.end());
        for(auto i = result.begin();i!=result.end();i++)
            cout<<*i;
    }
    else
    {
        for(auto i = result.begin();i!=result.end();i++)
            cout<<*i;
        reverse(result.begin(),result.end());
        result.erase(result.begin());
        for(auto i = result.begin();i!=result.end();i++)
            cout<<*i;
    }  
}
于 2016-11-24T05:14:13.930 に答える