学步园

最长公共子串（Longest common substring, 简称LCS）问题指的是求出给定的一组
字符串的长度最大的共有的子字符串。
举例说明，以下三个字符串的LCS就是 cde：
abcde
cdef
ccde

现在的情况是给你2个字符串，请找到他们的LCS

请注意：字符可以不相邻；

输入

输入第一行包含一个整数T，表示有T组数据；

对于每组数据包含2行，每行包含一个非空字符串，长度不超过1000个字符

输出

对于每组数据输出他们的LCS的长度.

样例输入

2 

abcde 

cdef 

aaaaaaa 

aaabaaa

样例输出

3 

6

LCS经典问题

#include<iostream>   
#include<string>  
#include<string.h> 
using   namespace   std;   
const   int   n=1002;   
int   c[n][n];   
char   str[n];   
int   lcs_len(string   a,string   b,int   c[][n])   
{   
	int   sa=a.length();   
	int   sb=b.length();   
	int   i,j;   
	for(i=0;i<=sa;++i)c[i][0]=0;   
	for(j=0;j<=sb;++j)c[0][j]=0;   
	for(i=1;i<=sa;++i)   
	{   
		for(j=1;j<=sb;++j)   
		{   
			if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;   
			else   if(c[i][j-1]>c[i-1][j])c[i][j]=c[i][j-1];   
			else   c[i][j]=c[i-1][j];   
		}   
	}   
	return   c[sa][sb];   
}   
char*bulid_lcs(char   str[],string   a,string   b)   
{   
	int   k,i=a.length(),j=b.length();   
	k=lcs_len(a,b,c);   
	str[k]='\0';   
	while(k>0)   
	{   
		if(c[i][j]==c[i-1][j])i--;   
		else   if(c[i][j]==c[i][j-1])j--;   
		else   
		{   
			str[--k]=a[i-1];   
			i--;j--;   
		}   
	}   
	return   str;   
}   
int   main()   
{  int number,te;
	string   a,b;
    cin>>number;
	for(te=1;te<=number;te++)
	{

	
	cin>>a;    
	cin>>b;   
	cout<<strlen(bulid_lcs(str,a,b))<<endl;
	}
	return   0;   
}