1808:公共子序列

描述

我們稱序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列當且僅當存在 嚴格上升 的序列< i1, i2, ..., ik >，使得對j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。

現在給出兩個序列X和Y，你的任務是找到X和Y的最大公共子序列，也就是說要找到一個最長的序列Z，使得Z既是X的子序列也是Y的子序列。

輸入

輸入包括多組測試資料。每組資料包括一行，給出兩個長度不超過200的字元串，表示兩個序列。兩個字元串之間由若幹個空格隔開。

輸出

對每組輸入資料，輸出一行，給出兩個序列的最大公共子序列的長度。

樣例輸入

abcfbc         abfcab
programming    contest 
abcd           mnp
      

樣例輸出

4
2
0      

當a[i]==b[j]  dp[i][j]=dp[i-1][j-1]+1;

   a[i]!=b[j]  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

代碼：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

int max(int a,int b)

{

    if(a>b)

    return a;

    else

    return b;

}

int count[201][201];

int main()

{

    char a[201],b[201];

    while(cin>>a>>b)

    {

         memset(count,0,sizeof(count));

         int len1=strlen(a);

         int len2=strlen(b);

         for(int i=1;i<=len1;i++)

         {

             for(int j=1;j<=len2;j++)

             {

                 if(a[i-1]==b[j-1])

                 {

                     count[i][j]=count[i-1][j-1]+1;

                 }

                 else

                 {

                    count[i][j]=max(count[i-1][j],count[i][j-1]);         

                 }

             }

         }

         cout<<count[len1][len2]<<endl;

    }

    return 0;

 }