最长公共子序列 tyvj1050
描述 Description
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad",顺次选1，3，5个字符就构成子串"cad",现给定两个字符串，求它们的最长共公子串。
输入格式 InputFormat
第一行两个字符串用空格分开。
输出格式 OutputFormat
最长子串的长度。
样例输入 SampleInput [复制数据]
abccd aecd
样例输出 SampleOutput [复制数据]
3
数据范围和注释 Hint
两个串的长度均小于2000
时间限制 TimeLimitation
各个测试点1s
这一题是很经典的动规了lcm[i][j]=max{ lcm[i-1][j-1]+1 (a[i]=b[j]),
lcm[i-1][j],lcm[i][j-1] (a[i]!=b[j]) }
lcm[i-1][j],lcm[i][j-1] (a[i]!=b[j]) }
唯一值得注意的是 C 选手如果用char数组的话，一定要把strlen(a)和strlen(b)用变量保存下来，不能直接写在循环里
//下面是错误的，因为strlen(char*)是以O(n)的效率计算的，每次O(n)就会超时
for(int i=0;i<strlen(a);i++)
for(int j=0;j<strlen(b);j++)
//下面是正确的写法
int lena=strlen(a);
int lenb=strlen(b);
for(int i=0;i<lena;i++)
for(int j=0;j<lenb;j++)
还有char要注意下标，因为后面要用到 -1 ，下标不能为负
当然也可以用string解决，慢不了多少，也蛮快的
C++ Code
/*
C++ Code
http://blog.csdn.net/jiangzh7
*/
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
string a,b;
int lcm[2010][2010];
int main()
{
freopen("ty1050.in","r",stdin);
freopen("ty1050.out","w",stdout);
cin>>a>>b;
a='0'+a;b='0'+b;//改成1基准，保证后面 -1 不越界
int maxx=0;
for(int i=1;i<=a.length();i++)
for(int j=1;j<b.length();j++)
{
if(a[i]!=b[j]) lcm[i][j]=max(lcm[i-1][j],lcm[i][j-1]);
else lcm[i][j]=max(lcm[i][j],lcm[i-1][j-1]+1);
maxx=max(maxx,lcm[i][j]);
}
printf("%d",maxx);
return 0;
}
