最长公共子序列

P1050 最长公共子序列

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad",顺次选1，3，5个字符就构成子串"cad",现给定两个字符串，求它们的最长共公子串。

输入格式

第一行两个字符串用空格分开。

输出格式

最长子串的长度。

测试样例1

输入

abccd aecd

输出

3

备注

两个串的长度均小于2000

 

 

---

 两个序列，一个长度为N，一个长度为M，f[i][j]表示第一个序列的前i个和第二个数列的前j个的最长公共子序列是多少

 那么对于每一个枚举到的i,j如果a[i] == b[j]  那么f[i][j] = max(f[i][j],f[i-1][j-1]+1)；否则的话f[i][j]=max(f[i-1][j],f[i][j-1])

 

//不能sort二维数组

//既然输入都用a+1了->strlen(a+1)

//这个东西不用找最大啊fnm就是最大的了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a[3005],b[3005];
int f[3005][3005],n,m;
int dp()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])
            {
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
}
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1),m=strlen(b+1);
    dp();
    cout<<f[n][m];
    puts("");
    return 0;
}