【動的計画】最長共通サブシーケンスの長さと最長文字列を求める

このアルゴリズムを検索できると信じているのは、きっとそれに接触しているに違いない.最長の共通サブシーケンス(非連続)問題は、2つの文字列の中で共通の文字からなる最長の文字列を求めることである(もちろん、文字の前後順は変えられない).
南陽36を例にとると:
 
 
最長共通サブシーケンス
時間制限:3000 ms|メモリ制限:65535 KB
難易度:3
説明
私たちは曲がらないで、問題のように、あなたがしなければならないのはプログラムを書いて、最も長い共通のサブシーケンスを得ることです.Tip:最長共通サブシーケンスは最長共通サブストリング(連続を必要としない)とも呼ばれ、英語ではLCS(Longest Common Subsequence)と略される.その定義は、1つのシーケンスSが、それぞれ2つ以上の既知のシーケンスのサブシーケンスであり、この条件に合致するすべてのシーケンスの中で最も長い場合、Sは既知のシーケンスの最も長い共通のサブシーケンスと呼ばれる.
入力
1行目には、整数N(0の次に、測定対象の2つの文字列のデータのセットごとに2行ずつ)が与えられる.各文字列の長さは1000以下である.
しゅつりょく
各テストデータのセットは、最長の共通サブシーケンス長を表す整数を出力します.各グループの結果が1行を占めます.
サンプル入力

2
asdf
adfsd
123abc
abc123abc

サンプル出力

3
6

 
この問題はa,bの2つの文字列の最大長を要求し,ここに最長文字列を求める.
arr[i][j]:
 
 
0
a
d
f
s
d
0
0
0
0
0
0
0
a
0
 
 
 
 
 
s
0
 
 
 
 
 
d
0
 
 
 
 
 
f
0
 
 
 
 
 
表の最初の列は文字列a:asdfです
表の最初の行は文字列b:adfsdです
arr[i][j]は、aの列がa[i]、bの列がb[j]のときのa,bの最長共通サブシーケンス長を表す.前から後へ配列を更新します.
 
 
0
a
d
f
s
d
0
0
0
0
0
0
0
a
0
1
1
1
1
1
s
0
 
 
 
 
 
d
0
 
 
 
 
 
f
0
 
 
 
 
 
2行目のaには1文字「a」しかないので、1行目がbの「a」に等しい場合、後ろは1になります.
 
 
0
a
d
f
s
d
0
0
0
0
0
0
0
a
0
1
1
1
1
1
s
0
1
2
2
2
2
d
0
 
 
 
 
 
f
0
 
 
 
 
 
同じように、3行目の最後の行は2を超えない.
 
 
0
a
d
f
s
d
0
0
0
0
0
0
0
a
0
1
1
1
1
1
s
0
1
2
2
2
2
d
0
1
2
2
2
3
f
0
1
2
3
3
3
 
更新が完了し、右下隅が共通サブ列の最大長になります.
図中の赤い数字の位置はa[i]=b[j]で、長さはa[i-1][j-1]に1を加え、(a[i]=b[j]をとると、長さが長くなり、この長さはa[i]、b[j]の前に斜め対角の位置になる)
a[i]!=b[j]ではarr[i][j]はmax[(a[0~i]とb[0~j-1]の最大長さ),(a[0~i-1]とb[0~j]の最大長さ)];
so:最大長を求めるコードは:
 

#include
#include   //memset     
using namespace std;
string a,b,s;
int al,bl,n;
int arr[1001][1001];

void dp()   //    
{
    for(int i=1;i<=al;i++)
    {
        for(int j=1;j<=bl;j++)
        {
            if(a[i-1]==b[j-1]) arr[i][j]=arr[i-1][j-1]+1;

              //i-1，j-1   a，b     0   

              //  arr     arr[1][1]    

              //  i=0||j=0→arr[i][j]=0;    
            else  arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
        }
    }
}

int main()
{
    while(cin>>n)
    {
        while(n--)
        {
            memset(arr,0,sizeof(arr));
            cin>>a>>b;
            al=a.length();
            bl=b.length();
            dp();
            cout<

次に、この最も長い文字列を求める方法を見てみましょう.
 
長さを求めるのは前から後ろへ配列を更新するが,文字列を要求するには後ろから前を見る必要がある.
 
 
0
a
d
f
s
d
0
0
0
0
0
0
0
a
0
1
1
1
1
1
s
0
1
1
2
2
2
d
0
1
2
2
2
3
f
0
1
2
3
3
3
図中の黄底赤字部分は等しい文字部分である:配列sで等しい点の文字を記録し、kはsの下付きで、初値は0である.
aの長さal,bの長さbl;i=al;j=bl;
判断a[i]=b[j]?等しい場合:s[k]=a[i]=b[j];k+1;ゆえに
等しくない場合:(1)arr[i][j]=arr[i-1][j]証明が上へ移動できる場合
(例:長さが4→2ではなく、3が抜けている)ので、このときは上へ進むことができます:i-;
(2)arr[i][j]!=arr[i-1][j]は、さらに上へ行くと等しい点が漏れていることを証明している.
s長が最大等しくない長さを求める.だから左へ:j--;
s=「dsa」を求める.
逆シーケンス探索なので文字列は逆シーケンスで、sを出力するときは逆シーケンスで出力します!
コードは次のとおりです.
 

#include
#include
using namespace std;
    string a,b,s;
    int al,bl,n;
    int arr[1001][1001];

void dp()
{
    for(int i=1;i<=al;i++)
    {
        for(int j=1;j<=bl;j++)
        {
            if(a[i-1]==b[j-1]) arr[i][j]=arr[i-1][j-1]+1;
            else  arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
        }
    }
}

int main()
{
    while(cin>>n)
    {
        while(n--)
        {
            memset(arr,0,sizeof(arr));
            cin>>a>>b;
            al=a.length();
            bl=b.length();
            dp();
            cout<=0;)
            {
                for(int j=bl;j>=0;)
                {
                    if(a[i]==b[j])
                    {
                        s[k]=a[i];
                        i--;
                        j--;
                        k++;
                    }
                    else
                    {
                        if(arr[i][j]==arr[i-1][j])
                            i--;
                        else
                            j--;
                    }
                }
            }
           cout<=0;k--)    //    s
                cout<