7-5 sdut-C语言实验-最长公共子序列
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子序列。（例子中的串不包含引号。）
编程求N个非空串的最长公共子序列的长度。限制：2<=N<=100；N个串中的字符只会是数字0，1，…，9或小写英文字母a，b，…，z；每个串非空且最多含100个字符；N个串的长度的乘积不会超过30000。
输入格式:
文件第1行是一个整数T，表示测试数据的个数（1<=T<=10）。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这些空格当然不算作串的一部分。
输出格式:
输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子序列的长度。
输入样例:
1. 1 2. 3 3. ab 4. bc 5. cd
输出样例:
0
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include<stdio.h> #include<string.h> char s[200][200]; int len[200]; int dp[40000]; int n; int k; int max2(int x,int y){ return x>y?x:y; } int LCS(int x[]) //此方法从每个字符串的尾部开始计算，所以x记录的是当前字符串的这一个子串的起始位置 { int i,j,t; int a;//a标识当前序列乘积的编号 int b;//b标识公共子序列一共有多长了 //如果有串长度为0，那么没有公共子序列，公共子序列长度为零 for(i=1; i<=n; i++) { if(x[i]==0) { return 0; } } //寻找当前的状态 //a在第n个字符串的最后一位，其位置乘以串的长度，往前递推 //最终得到了一个唯一的乘积，唯一标识现在的n个字符串的状态 //例如第一个串长3，第二个长4，而第三个长5，此时a便是记录这样的状态 for(a=x[n]-1,i=n-1; i>=1; i--) { a=a*len[i]+x[i]-1;//类似于进制转化，消除冲突的过程 } if(dp[a]>=0)//记忆化搜索//第一轮都等于-1，后期有所变化 { return dp[a]; } //检查当前n组字符串的最后一个字母，如果都相等，则i会等于n+1，进入下面情况一 //否则进入情况二 for(i=2; i<=n; i++) { if(s[1][x[1]-1]!=s[i][x[i]-1]) { break; } } //情况一，相等的话就是dp[i-1][j-1]+1这个过程,几个字符串就是几维的dp if(i>n) { for(j=1; j<=n; j++) { x[j]--; }//就是让n组字符串都忽略掉最后一位，就都变成了求长n-1的字符串，递推地往前求 b=LCS(x)+1;//这时候lcs传入的是n-1的字符串， //b即为dp[i-1][j-1]+1 for(j=1; j<=n; j++) { x[j]++; }//算完后回溯 } //不相等就是dp[i][j]=max(dp[i-1][j],dp[i][j-1])这个过程 else { b=0; for(j=1; j<=n; j++) { x[j]--; //假设对n组字符串求公共子序列，此时j=1，传入lcs函数，这时 //1号字符串长度为n-1，其他都为n //保持这个状态来到这里，如果还执行1号字符串的删减， //则一号字符串变为n-2，其他还为n //或者此时执行二号删减，二号字符串变为n-1，一号之前减过也为n-1 //其他的则为n，这样可以把字符串长短不一的情况都遍历一遍 //类似于dp[i-1][j],dp[i][j-1]这样的尝试 t=LCS(x);//带入函数 b=max2(t,b);//判断子序列最长的情况 x[j]++;//回溯 } } dp[a]=b;//记录当前n组字符串相应的公共子序列对应的长度 return b; } int main() { int t,i; int m[200]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%s",s[i]); len[i]=strlen(s[i]);//固定长度 m[i]=strlen(s[i]);//每个串的位置 } memset(dp,-1,sizeof(dp)); printf("%d\n",LCS(m));//max } return 0; }
