Blog·Tanky WooABOUTRSS

百练oj2806 最长公公子序列

15 May 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

//ID:百练oj2806 最长公公子序列 //网站:C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛 //地址:http://www.cppleyuan.com/ //个人主页:www.wutianqi.com

#include
#include

#include
#include
#include
#include
using namespace std;
#define MAX_LEN 1000
char sz1[MAX_LEN];
char sz2[MAX_LEN];
int aMaxLen[MAX_LEN][MAX_LEN];

int main()
{
    while(scanf("%s%s", sz1+1, sz2+1) == 2)
    {
        int nLength1 = strlen(sz1+1);  //
        int nLength2 = strlen(sz2+1);  //
        int i, j;
        for(i = 0; i <= nLength1; i++)
            aMaxLen[i][0] = 0;
        for(j = 0; j <= nLength2; j++)
            aMaxLen[0][j] = 0;
        for(i = 1; i <= nLength1; i++)
            for(j = 1; j <= nLength2; j++)
                if(sz1[i] == sz2[j])
                    aMaxLen[i][j] = aMaxLen[i-1][j-1] + 1;
                else
                {
                    int nLen1 = aMaxLen[i-1][j];
                    int nLen2 = aMaxLen[i][j-1];
                    if(nLen1 > nLen2)
                        aMaxLen[i][j] = nLen1;
                    else
                        aMaxLen[i][j] = nLen2;
                }
        printf("%d\n", aMaxLen[nLength1][nLength2]);
    }
    return 0;
}