精华内容
下载资源
问答
  • 最长公共子序列C语言代码

    千次阅读 2018-04-21 12:46:05
    #include<stdio.h> #include<string.h> int c[200][200]; //用c[i][j]记录X[i]与Y[j] 的LCS 的长度 int b[200][200]; //b[i][j]记录c[i][j]是通过哪一个子问题的值求得的,以...
    1. #include<stdio.h>  
    2. #include<string.h>  
    3. int c[200][200];   //用c[i][j]记录X[i]与Y[j] 的LCS 的长度  
    4. int b[200][200];   //b[i][j]记录c[i][j]是通过哪一个子问题的值求得的,以决定搜索的方向  
    5. char f[200];  
    6.   
    7. /*-----------------------分割线--------------------------------*/  
    8.   
    9. /*取c[i-1][j]和c[i][j-1]的最大值,并记录c[i][j]是通过哪一个子问题的值求得的,以决定搜索的方向*/  
    10. int Max(int m,int n,int i,int j)  
    11. {  
    12.     if(m > n)  
    13.     {  
    14.         b[i][j] = -1;  
    15.         return m;  
    16.     }  
    17.     else  
    18.     {  
    19.         b[i][j] = 1;  
    20.         return n;  
    21.     }  
    22. }  
    23. /*-----------------------分割线--------------------------------*/  
    24. /*递归打印LCS的元素内容*/  
    25. void print(int i,int j,int s,char x[],char y[])  
    26. {  
    27.     if(b[i][j] == 0)  
    28.     {  
    29.         f[s-1] = x[i-1];  
    30.         i--;j--;s--;  
    31.         print(i,j,s,x,y);  
    32.     }  
    33.     else if(b[i][j] == -1)  
    34.     {  
    35.         i--;  
    36.         print(i,j,s,x,y);  
    37.     }  
    38.     else if(b[i][j] == 1)  
    39.     {  
    40.         j--;  
    41.         print(i,j,s,x,y);  
    42.     }  
    43. }  
    44. /*-----------------------分割线--------------------------------*/  
    45. int LCS(char x[],char y[])  
    46. {  
    47.     int i,j;  
    48.     int x_len,y_len;  
    49.     x_len = strlen(x);  
    50.     y_len = strlen(y);  
    51.     printf("   ");  
    52.     for(i = 0;i < y_len;i++)  
    53.     {  
    54.         printf("%c  ",y[i]);  
    55.     }  
    56.     printf("\n");  
    57.     for(i = 1;i <= x_len;i++)  
    58.     {  
    59.         printf("%c  ",x[i-1]);  
    60.         for(j = 1;j <= y_len;j++)  
    61.         {  
    62.             if(x[i-1] == y[j-1])  
    63.             {  
    64.                 c[i][j] = c[i-1][j-1] +1;  
    65.                 b[i][j] = 0;  
    66.                 printf("%d  ",c[i][j]);  
    67.             }  
    68.             else  
    69.             {  
    70.                 c[i][j] = Max(c[i-1][j],c[i][j-1],i,j);  
    71.                 printf("%d  ",c[i][j]);  
    72.             }  
    73.         }  
    74.         printf("\n");  
    75.     }  
    76.     /*-------------------------分割线---------------------------------------*/  
    77.     //打印X和Y的LCS  
    78.     printf("X和Y的LCS是:");  
    79.     print(x_len,y_len,c[x_len][y_len],x,y);  
    80.     printf("%s",f);  
    81.     printf("\n");  
    82.     return c[x_len][y_len];  
    83. }  
    84.   
    85. /*------------------------------分割线----------------------------------------*/  
    86. void main()  
    87. {  
    88.     char X[200],Y[200];  
    89.     int i,j,s;  
    90.     printf("请输入字符串X:");  
    91.     scanf("%s",X);  
    92.     while(strlen(X) > 200)  
    93.     {  
    94.         printf("您输入的字符串超过最大长度,请重新输入!");  
    95.         scanf("%s",X);  
    96.     }  
    97.     printf("请输入字符串Y:");  
    98.     scanf("%s",Y);  
    99.     while(strlen(Y) > 200)  
    100.     {  
    101.         printf("您输入的字符串超过最大长度,请重新输入!");  
    102.         scanf("%s",Y);  
    103.     }  
    104.     s = LCS(X,Y);  
    105.     printf("X和Y的LCS: %d \n",s);  
    106. }  
    展开全文
  • 最长公共子序列 & 最长公共子串的区别:找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。leetcode 1143题 最长公共子序列!!!字符可以不连续给定两个字符串 ...

    最长公共子序列 & 最长公共子串的区别:

    找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。

    leetcode 1143题 最长公共子序列

    !!!字符可以不连续

    给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。

    一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

    例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

    若这两个字符串没有公共子序列,则返回 0。

    示例 1:

    输入:text1 = “abcde”, text2 = “ace”

    输出:3

    解释:最长公共子序列是 “ace”,它的长度为 3。

    示例 2:

    输入:text1 = “abc”, text2 = “abc”

    输出:3

    解释:最长公共子序列是 “abc”,它的长度为 3。

    示例 3:

    输入:text1 = “abc”, text2 = “def”

    输出:0

    解释:两个字符串没有公共子序列,返回 0。

    提示:

    1 <= text1.length <= 1000

    1 <= text2.length <= 1000

    输入的字符串只含有小写英文字符。

    # leetcode submit region begin(Prohibit modification and deletion)

    class Solution(object):

    def longestCommonSubsequence(self, text1, text2):

    """

    :type text1: str

    :type text2: str

    :rtype: int

    """

    t1,t2 = len(text1),len(text2)

    dp = [[0 for j in range(t2+1)] for i in range(t1+1)]

    # 0行和0列都是字符串和空字符比较,为0

    for i in range(1,t1+1):

    for j in range(1,t2+1):

    # 如果匹配 则移除i,j对应的字符,结果+1

    # 然后再去找之前的最大值

    if text1[i-1]==text2[j-1]:

    dp[i][j] = 1 + dp[i-1][j-1]

    else:

    # 如果不匹配,则为0, 去找左边或者右边最大值

    dp[i][j] = max(dp[i-1][j],dp[i][j-1])

    #print(dp[i][:])

    return(dp[-1][-1])

    # leetcode submit region end(Prohibit modification and deletion)

    字符串a,b中的最长公共子串

    题目描述

    查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。

    输入描述:

    输入两个字符串

    输出描述:

    返回重复出现的字符

    while True:

    try:

    str1,str2 = input(),input()

    # 短的为text1 长的为text2

    text1, text2 = (str1, str2) if len(str1) < len(str2) else (str2, str1)

    t1,t2 = len(text1),len(text2)

    dp = [[0 for j in range(t2+1)] for i in range(t1+1)]

    maxlen = 0

    for i in range(1,t1+1):

    for j in range(1,t2+1):

    # 如果匹配 则移除i,j对应的字符,去找之前的最大值

    if text1[i-1]==text2[j-1]:

    dp[i][j] = 1 + dp[i-1][j-1]

    if dp[i][j]>maxlen:

    # 记录最长公共子串的长度

    maxlen = dp[i][j]

    start = i - maxlen

    # 如果不匹配,则为0

    print(text1[start:start+maxlen])

    except:

    break

    最长上升子序列

    给定一个无序的整数数组,找到其中最长上升子序列的长度。

    示例:

    输入: [10,9,2,5,3,7,101,18]

    输出: 4

    解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    说明: 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。

    # 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

    # Related Topics 二分查找 动态规划

    # leetcode submit region begin(Prohibit modification and deletion)

    class Solution(object):

    def lengthOfLIS(self, nums):

    """

    :type nums: List[int]

    :rtype: int

    """

    if len(nums) == 0:

    return 0

    n = len(nums)

    lengths = [1 for _ in range(n)]

    for i in range(1,n):

    for j in range(i):

    # 坐标锁定在i, 然后遍历j(从0->i-1)

    if nums[j] < nums[i]:

    lengths[i] = max(lengths[j] + 1,lengths[i])

    #print(lengths)

    return(max(lengths))

    # leetcode submit region end(Prohibit modification and deletion)

    展开全文
  • 思路: 有两个字符数组a,b 分为三种情况: 比较a,b数组当前长度的最后一个字符...不相等,把a数组的最后一个字符去掉的最长公共子序列大于把b数组的最后一个字符去掉的最长公共子序列 即:当lsc[i-1][j]&g...

    思路:
    有两个字符数组a,b
    分为三种情况:
    比较a,b数组当前长度的最后一个字符

    1. 相等时, lsc值等于前一段值加1
      即:当a[i-1]==b[j-1]时(因为i,j是从1开始,所以是a[i-1],b[j-1]),lsc[i][j]=lsc[i-1][j-1]+1
    2. 不相等,把a数组的最后一个字符去掉的最长公共子序列大于把b数组的最后一个字符去掉的最长公共子序列
      即:当lsc[i-1][j]>=lsc[i][j-1]时,lsc[i][j]=lsc[i-1][j]
    3. 不相等,把b数组的最后一个字符去掉的最长公共子序列大于把a数组的最后一个字符去掉的最长公共子序列
      即:当lsc[i-1][j]<lsc[i][j-1]时,lsc[i][j]=lsc[i][j-1]

    代码:

    #include <stdio.h>
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    void LSCLength(char a[],char b[],int c[11][10],int lsc[11][10],int la,int lb)
    {
    	for(int i=0;i<=la;i++)	lsc[0][i]=0;
    	for(int i=0;i<=lb;i++)	lsc[i][0]=0;
    	for(int i=1;i<=la;i++)
    	{
    		for(int j=1;j<=lb;j++){
    			if(a[i-1]==b[j-1])
    			{
    				lsc[i][j]=lsc[i-1][j-1]+1;
    				c[i][j]=1;
    			}
    			else if(lsc[i-1][j]>=lsc[i][j-1])
    			{
    				lsc[i][j]=lsc[i-1][j];
    				c[i][j]=2;
    			}
    			else{
    				lsc[i][j]=lsc[i][j-1];
    				c[i][j]=3;
    			}
    		}
    	}
    
    	
    }
    void LSC(int i,int j,char a[],int c[11][10]) 
    {
    	if(i==0 || j==0)	return;
    	if(c[i][j]==1)
    	{
    		LSC(i-1,j-1,a,c);
    		printf("%3c  ",a[i-1]);
    	}
    	else if(c[i][j]==2)
    	{
    		LSC(i-1,j,a,c);
    	}
    	else
    	{
    		LSC(i,j-1,a,c);
    	}
    	
    }
    int main(int argc, char** argv) {
    	char a[10]={'d','i','d','a','c','t','i','c','a','l'};
    	char b[9]={'a','d','v','a','n','t','a','g','e'};
    	int c[11][10]={0};
    	int lsc[11][10]={0};
    	LSCLength(a,b,c,lsc,10,9);
    	for(int i=0;i<=10;i++)
    	{
    		for(int j=0;j<=9;j++)
    		{
    			printf("%d  ",lsc[i][j]);
    		}
    		printf("\n");
    	}
    	printf("长度:%d\n比较情况\n",lsc[10][9]);
    	
    	for(int i = 0;i<11;i++){
    		for(int j = 0;j<10;j++){
    			printf("%3d",c[i][j]);
    		}
    		printf("\n");
    	}
    	LSC(10,9,a,c);
    	return 0;
    } 
    

    运行结果:
    在这里插入图片描述

    展开全文
  • C语言最长公共序列代码 C语言最长公共序列代码 C语言最长公共序列代码
  • 最长公共子序列C语言

    千次阅读 2018-11-03 11:57:11
    问题: 设X有m个元素,Y有n个元素,求得X和Y的最长公共子序列。 注意:这问题如果用蛮力算法,时间复杂度是指数级别的,不太好。 考虑一下子问题之间的依赖关系(设Z是X和Y的最长公共子序列,有k个元素): 若X最后...

    问题: 设X有m个元素,Y有n个元素,求得X和Y的最长公共子序列。

    注意:这问题如果用蛮力算法,时间复杂度是指数级别的,不太好。

    考虑一下子问题之间的依赖关系(设Z是X和Y的最长公共子序列,有k个元素):

    • 若X最后一个元素==Y最后一个元素,则Z(k-1)是X(m-1)和Y(n-1)的最长公共子序列。
    • 若X最后一个元素!=Y最后一个元素,则Z可以是X(m-1)和Y的最长公共子序列。
    • 若X最后一个元素!=Y最后一个元素,则Z可以是X和Y(n-1)的最长公共子序列。

    所以:这个问题满足优化原则和子问题重叠性,可以用动态规划解决它。

    最长公共子序列的长度的递推方程(令m = i;n = j;):

    在这里插入图片描述

    在这里插入图片描述
    可惜的是这个方法有一些缺陷,当最长公共子序列的解不唯一的时候,这个代码只能求出一个解。

    #include<iostream>
    #include<string.h> 
    using namespace std;
    #define MAXSIZE 100
    int B[MAXSIZE][MAXSIZE];		  //B数组用来追踪最长子序列 
    
    void Trace(char*X,int i,int j){
    	if(i == 0||j == 0){
    		return;
    	}	
    	if(B[i][j] == 0){//0代表左斜向上
    		Trace(X,i-1,j-1);
    		cout<<X[i-1]<<" ";
    	}
    	else if(B[i][j] == 1){//1代表向上
    		Trace(X,i-1,j);
    	}
    	else{//2代表向左
    		Trace(X,i,j-1);
    	} 
    } 
    
    
    void LCS(char *X,char *Y,int m,int n){
    	int C[m+1][n+1]; 
    	for(int i = 0;i <= m;i++){
    		for(int j = 0;j <= n;j++){
    			if(i ==0||j == 0){
    				C[i][j] = 0;
    			}
    			else if(X[i-1] == Y[j-1]){
    				C[i][j] = C[i-1][j-1] + 1;
    				B[i][j] = 0; //0代表左斜向上	
    			}
    			else{
    				if(C[i-1][j] >= C[i][j-1]){
    					C[i][j] = C[i-1][j];
    					B[i][j] = 1; //1代表向上 
    				}
    				else{
    					C[i][j] = C[i][j-1];
    					B[i][j] = 2; //2代表向左 
    				}
    			}
    		}
    	}	
    }
    
    int main(){
    	char X[] = "ABCBDAB";
    	char Y[] = "BDCABA";
    	/*当把一二行的代码换成注释中的代码(即X,Y互换),结果可能会有变化
    	char Y[] = "ABCBDAB";
    	char X[] = "BDCABA";
    	*/
    	int m = strlen(X),n = strlen(Y);
    	LCS(X,Y,m,n);
    	Trace(X,m,n);
    	return 0;
    	//实际上是有三个解:
    	//BCBA
    	//BDAB
    	//BCAB
    }
    

    参考资料:
    中国大学MOOK 算法设计与分析 5.8

    展开全文
  • 利用动态规划的思想,通过设置一个临时数组t[][],其中t[i][j]表示,以Str1[i]作为末尾和以Str[2]作为末尾的最长公共子序列或者子串的长度。 算法步骤: (1)将输入的两个字符串分别存在数组a[]和b[]中,同时设置两...
  • 一、求最长公共子序列 1、问题描述: 从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串...
  • 最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
  • 最长公共子序列 最长公共子序列的求解,如下图所示: 可以看到,最长公共子序列的依赖关系如上图所示,[i,j]的值取决于{[i-1,j-1],[i,j-1],[i-1,j]} 实现方法如下: LCS_len.h #include #include #include #define ...
  • 算法分析课程作业,C语言编写,可能需要用input.txt输入,最长公共子序列问题代码
  • 最长公共子序列C语言) 算法-动态规划:算法与数据结构参考 题目: 给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , ...
  • 最长公共子序列代码

    2008-04-24 10:29:39
    最长公共子序列代码(c语言)
  • 给定两个字符串text1 和text2,返回这两个字符串的最长公共子序列。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新...
  • 可以根据里面代码修改具体输出,实现过程根据《算法导论》
  • 本内容将介绍最长公共子序列和最长公共子串的动态规划解法。
  • 动态规划最长公共子序列C语言

    千次阅读 2018-09-08 12:59:43
    #include &amp;quot;stdafx.h&amp;quot; #include&amp;amp;lt;stdio.h&amp;amp;gt; #define m 7 #define n 6 int c[m + 1][n + 1]; int b[m+1][n+1]; void LCS_LENGTH(char *x,char *y) ... i++)
  • /b说明,当为0时方向为左上角,为1时方向为左为2时方向为上 void LCS(char* x,char* y,int lenx,int leny,int c[][100],int b[][100]){  for(int i=1;i&lt;=leny;i++){  c[0][i] = 0;  } ...
  • 主要给大家介绍了如何利用C++实现最长公共子序列与最长公共子串,文章一开始就给大家简单的介绍了什么是子序列,子串应该比较好理解就不用多介绍了,人后通过算法及示例代码详细介绍了C++实现的方法,有需要的朋友们...
  • 分析并掌握“最长公共子序列” 问题的动态规划算法求解方法; 最长公共子序列问题:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1...
  • C语言最长公共子序列

    千次阅读 2018-11-27 22:34:49
    下面是一段自写代码的呈现,如果后期有不明白,自己查阅收藏博客 主要方法:画出表格图,列出递归公式 自写1: #include&lt;stdio.h&gt; #include&lt;string.h&gt; void print(int i, int j, int s...
  • 一.前言 如上 ...//求最长公共子序列的长度 //#include<string.h> int main(){ int max(int a,int b); int i;//循环变量 int j;//循环变量 int a[7][8]; char s2[7];//B char s1[8];//A
  • 主要功能:递归法解最长公共子序列问题 #include&amp;amp;lt;stdio.h&amp;amp;gt; #include&amp;amp;lt;string.h&amp;amp;gt; /* 递归思路: 当数组a和b对应位置字符相同时,则直接求解下一个位置;...
  • 算法提高 最长字符序列 时间限制:1.0s 内存限制:256.0MB    最长字符序列 问题描述  设x(i), y(i), z(i)表示单个字符,则X={x(1)x(2)……x(m)},Y={y(1)y(2)……y(n)},Z={z(1)z(2)……z(k)},我们称其为...
  • 计算最长公共子序列

    千次阅读 2018-09-03 20:42:27
    好比一个数列 S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S 称为已知序列的最长公共子序列。 如何解决 通用的解法用动态规划,如何使用动态规划解题,晚上已经有很多不同人的...
  • 动态规划解最长公共子序列问题(LCS)C语言加注释

    万次阅读 多人点赞 2015-10-27 14:56:13
    【问题】 求两字符序列的最长公共字符子序列 问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1...
  • 最长公共子序列问题:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,235
精华内容 894
关键字:

最长公共子序列c语言代码

c语言 订阅