精华内容
下载资源
问答
  • 从1开始为后边比较i-1准备,求得一个矩阵最右下角表示公共字符个数(规则:从f[1][1]开始,如果a和b字符对应相等,就等于其左上角的数加1,不相等时取上边和左边大的值)
  • 思路: 有两个字符数组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语言代码

    千次阅读 2018-04-21 12:46:05
    #include&lt;stdio.h&gt; #include&lt;string.h&gt; 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. }  
    展开全文
  • 最长公共子序列问题C语言#include#include#includeint num[50][50]={0};int b[50][50]={0};int lcsLength(char *x,char *y,int xLen,int yLen);void LCS(int i,int j,char *x);int lcsLength(char *x,char *y,int ...

    最长公共子序列问题C语言

    #include#include#includeint num[50][50]={0};

    int b[50][50]={0};

    int lcsLength(char *x,char *y,int xLen,int yLen);

    void LCS(int i,int j,char *x);

    int lcsLength(char *x,char *y,int xLen,int yLen){

    int m=xLen-1;

    int n=yLen-1;

    for(int i=0;i<=m;i++){

    for(int j=0;j<=n;j++){

    if(x[i]==y[j]){

    num[i][j]=num[i-1][j-1]+1;

    b[i][j]=1;

    }else if(num[i-1][j]>=num[i][j-1]){

    num[i][j]=num[i-1][j];

    b[i][j]=2;

    }else{

    num[i][j]=num[i][j-1];

    b[i][j]=3;

    }

    }

    }

    测试正确性的矩阵图

    printf("num表为:\n");

    for(int i=0;i<=m;i++){

    for(int j=0;j<=n;j++){

    printf("%d",num[i][j]);

    }

    printf("\n");

    }

    printf("b表为:\n");

    for(int i=0;i<=m;i++){

    for(int j=0;j<=n;j++){

    printf("%d",b[i][j]);

    }

    printf("\n");

    }

    /

    return num[m][n];

    }

    void LCS(int i,int j,char *x){

    if(i<0||j<0) return ;

    if(b[i][j]==1){

    LCS(i-1,j-1,x);

    printf("%c",x[i]);

    }else if(b[i][j]==2){

    LCS(i-1,j,x);

    }

    else LCS(i,j-1,x);

    }

    void main(){

    char x[50],y[50];

    printf(“请输入字符串X:”);

    scanf("%s",x);

    while(strlen(x) > 50)

    {

    printf(“您输入的字符串超过最大长度,请重新输入!”);

    scanf("%s",x);

    }

    printf(“请输入字符串Y:”);

    scanf("%s",y);

    while(strlen(y) > 50)

    {

    printf(“您输入的字符串超过最大长度,请重新输入!”);

    scanf("%s",y);

    }

    int xLen=strlen(x);

    int yLen=strlen(y);

    printf(“LCS长度为%d\n”,lcsLength(x,y,xLen,yLen));

    LCS(xLen-1,yLen-1,x);

    system("pause");

    }

    9f13f82c0c522f8cb4ec5624bad32d8e.png

    展开全文
  • 最长公共子序列 & 最长公共子串的区别:找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。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)

    展开全文
  • 最长公共子序列c语言编程。求最长公共子序列c语言编程。求最长公共子序列c语言编程。求最长公共子序列c语言编程。求最长公共子序列c语言编程。
  • C语言最长公共序列代码 C语言最长公共序列代码 C语言最长公共序列代码
  • 利用动态规划的思想,通过设置一个临时数组t[][],其中t[i][j]表示,以Str1[i]作为末尾和以Str[2]作为末尾的最长公共子序列或者子串的长度。 算法步骤: (1)将输入的两个字符串分别存在数组a[]和b[]中,同时设置两...
  • 最长公共子序列C语言

    千次阅读 2018-11-03 11:57:11
    问题: 设X有m个元素,Y有n个元素,求得X和Y的最长公共子序列。 注意:这问题如果用蛮力算法,时间复杂度是指数级别的,不太好。 考虑一下子问题之间的依赖关系(设Z是X和Y的最长公共子序列,有k个元素): 若X最后...
  • 一、求最长公共子序列 1、问题描述: 从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串...
  • 最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
  • 最长公共子序列问题C语言 #include<stdio.h> #include<stdlib.h> #include<string.h> int num[50][50]={0}; int b[50][50]={0}; int lcsLength(char *x,char *y,int xLen,int yLen); void LCS(int...
  • 最长公共子序列C语言

    千次阅读 2017-08-03 23:58:57
    这个系列的内容均出自《算法设计与问题求解》,有兴趣的可以去看原版书。 输出: 4C(x,y) = 0 当 i=0, j=0时 C(i-1,j-1)+1 当i,j>0,Xi=Yi时 max{C(i-1, j), C(i, j-1)} 当i,j>0, Xi!=Yj时#include ...
  • 最长公共子序列 最长公共子序列的求解,如下图所示: 可以看到,最长公共子序列的依赖关系如上图所示,[i,j]的值取决于{[i-1,j-1],[i,j-1],[i-1,j]} 实现方法如下: LCS_len.h #include #include #include #define ...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , ...
  • 最长公共子序列C语言) 算法-动态规划:算法与数据结构参考 题目: 给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变...
  • C语言最长公共子序列问题的算法实现。LCS问题,没有太多的描述语言了,这个资源很简单的。
  • #include <stdio.h> #include <string.h> char a[100],b[100],f[100][100],c[100]; void maxnum(int l1,int l2) { int i=0,j=0; for(i=1;i<=l1;i++) { for(j=1;... if(...
  • 给定两个字符串text1 和text2,返回这两个字符串的最长公共子序列。 一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新...

空空如也

空空如也

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

最长公共子序列c语言

c语言 订阅