最长公共子序列

#include <stdio.h>
#include <string.h>
int sum[110][110];
int pt[110][110];
char s[110][110];
int main()
{
int f(char s1[110],char s2[110]);
int i,n,m,t;
scanf(“%d”,&t);
while(t–)
{
scanf(“%d”,&n);
for(i=0; i<=n-1; i++)
{
scanf(“%s”,s[i]);
}
for(i=1; i<=n-1; i++)
{
m=f(s[0],s[i]);//一个一个的比较
if(m0)
{
break;
}
}
printf(“%d\n”,m);
}
return 0;
}
int f(char s1[110],char s2[110])
{
int len1=strlen(s1);
int len2=strlen(s2);
char s3[110];
int i,j,x,key,val,y,len,max;
memset(sum,0,sizeof(sum));
memset(pt,0,sizeof(pt));
for(i=1; i<=len1; i++)
{
for(j=1; j<=len2; j++)
{
max=0;
for(x=1; x<=3; x++) //两种状态 a[i]=b[j]：sum[i-1][j-1]+1 a[i]!=b[j]：sum[i-1][j]||sum[i][j-1]
{
if(x1)
{
if(s1[i-1]s2[j-1])
{
val=sum[i-1][j-1]+1;
}
else
{
val=sum[i-1][j-1];
}
}
else if(x2)
{
val=sum[i][j-1];
}
else
{
val=sum[i-1][j];
}
if(val>max)
{
max=val;
key=x; //key记录下取值的方式，以便还原最长公共字符串
}
}
sum[i][j]=max;
pt[i][j]=key;
}
}
x=len1;
y=len2;
len=sum[len1][len2];
len–;
s3[sum[len1][len2]]=‘\0’;
for(i=1; i<=sum[len1][len2]; i++) //按照保存好的key还原字符串
{
while(s1[x-1]!=s2[y-1])
{
key=pt[x][y];
if(key1)
{
x–;
y–;
}
else if(key2)
{
y–;
}
else
{
x–;
}
}
s3[len]=s1[x-1];
len–;
key=pt[x][y];
if(key1)
{
x–;
y–;
}
else if(key2)
{
y–;
}
else
{
x–;
}
}
strcpy(s[0],s3); //将最长公共字符串赋给s[0]以便与后续字符串比较
return sum[len1][len2];
}