最長公共子序列——Common Subsequence

問題 A: Common Subsequence

時間限制: 1 Sec  記憶體限制: 128 MB

送出: 7  解決: 5

[送出][狀态][讨論版][命題人:add_lwn]

題目描述

給定序列的子序列是将給定的序列的一些元素（可能沒有）省去。給定一個序列X = <x1, x2, ..., xm>另一個序列Z = <z1, z2, ..., zk>是X的子序列存在一個X的指數的嚴格遞增的序列<i1, i2, ..., ik>，對于所有的j = 1,2,...,k, xij = zj。例如，Z = <a, b, f, c>，是X = <a, b, c, f, b, c>的子序列，其索引序列<1, 2, 4, 6>。給定兩個序列X和Y，問題是求出X和Y的最大公子序列的長度。

程式輸入來自一個文本檔案。檔案中的每個資料集包含兩個字元串，表示給定的序列。這些序列由任意數量的空格分隔。輸入資料是正确的。對于每一組資料，每行列印最長度公共子序列的長度。

輸入

輸出

樣例輸入

abcfbc abfcab
programming contest 
abcd mnp      

樣例輸出

4
2
0      

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
char a[1000],b[1000];
int lena,lenb;
int dp[1000][1000];
int main()
{
    while(cin>>a)
    {
        cin>>b;
        lena=strlen(a);
        lenb=strlen(b);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<lena;i++)
            for(int j=0;j<lenb;j++)
            {
                if(a[i]==b[j])
                    dp[i+1][j+1]=dp[i][j]+1;
                else
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        cout<<dp[lena][lenb]<<endl;
    }
    return 0;
}