7-5 sdut-C语言实验-最长公共子序列

简介: 7-5 sdut-C语言实验-最长公共子序列

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;
}
目录
相关文章
|
4月前
|
BI
7-6 sdut-C语言实验-最长上升子序列
7-6 sdut-C语言实验-最长上升子序列
32 1
|
4月前
7-2 sdut-C语言实验-删数问题(贪心法二)
7-2 sdut-C语言实验-删数问题(贪心法二)
37 2
|
算法 搜索推荐 程序员
C语言第十四练——请输入一个数的逆序数
C语言第十四练——请输入一个数的逆序数
121 0
|
4月前
|
BI
7-6 sdut-C语言实验-最长上升子序列的和
7-6 sdut-C语言实验-最长上升子序列的和
34 2
|
4月前
|
BI
7-7 sdut-C语言实验-上升子序列
7-7 sdut-C语言实验-上升子序列
28 0
|
4月前
|
开发工具 git
7-4 sdut-C语言实验-最长公共子序列
7-4 sdut-C语言实验-最长公共子序列
52 1
|
4月前
7-4 sdut-C语言实验-区间覆盖问题
7-4 sdut-C语言实验-区间覆盖问题
31 2
|
4月前
|
算法
7-2 sdut-C语言实验-数字三角形问题
7-2 sdut-C语言实验-数字三角形问题
25 1
|
4月前
7-8 sdut-C语言实验-取数字问题
7-8 sdut-C语言实验-取数字问题
28 2
|
4月前
7-10 sdut-C语言实验-走迷宫
7-10 sdut-C语言实验-走迷宫
30 2