LCS 最长公共子序列

绝地灬酷狼 2022-08-03 14:57 155阅读 0赞

首先要明白什么是子序列，什么是子串；

设：主串长度为n；

子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

例：主串为abdexk

那么在子序列中若有a，则a必须在所有其他元素的前面，若有b，除了a，b排在最前面............（相对位置不变）

子串：从主串中抽出少于n的元素组成的序列（这写被抽出来的元素必须是连续的，相对位置不变）；

例：主串为afoijnc

那么在子串中，若有a和i，则子串中必有一段时afoi，不会出现afi、aoi或ai的的情况。

最长公共子序列的求法网上有很多，这里不多做解释，直接上模板了。

（目前为止只知道这一个）

#define maxx(a,b) (a>b?a:b)
    char s1[1200],s2[1200];
    int p[1200][1200];
    void LCS(){
    	int len1=strlen(s1);
    	int len2=strlen(s2);
    	int i,j;
    	for(i=1;i<=len1;i++){
    		for(j=1;j<=len2;j++){
    			if(s1[i-1]==s2[j-1])
    				p[i][j]=p[i-1][j-1]+1;
    			else
    				p[i][j]=maxx(p[i-1][j],p[i][j-1]);
    		}
    	}
    }

以上这种会超内存，下面给出优化版

#define maxx(a,b) (a>b?a:b)
    char s1[1200],s2[1200];
    int p[2][1200];											
    void LCS(){
    	int len1=strlen(s1);
    	int len2=strlen(s2);
    	int i,j;
    	for(i=1;i<=len1;i++){
    		for(j=1;j<=len2;j++){
    				int x=i%2;					//滚动数组
    				int y=1-x;
    			if(s1[i-1]==s2[j-1])
    				p[x][j]=p[y][j-1]+1;
    			else
    				p[x][j]=maxx(p[y][j],p[x][j-1]);
    		}
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子序列（LCS）与最长公共子串(DP)

《1》[最长公共子序列（LCS）与最长公共子串(DP)][LCS_DP] http://blog.csdn.net/u012102306/article/details/53

亦凉/ 2024年02月19日 13:24/ 0 赞/ 6 阅读

相关最长公共子序列（LCS）

最长公共子序列（LCS） problem [leetcode: 1035. 不相交的线][leetcode_ 1035.] > dp\[i\]\[j\]：nums

朴灿烈づ我的快乐病毒、/ 2022年10月14日 13:54/ 0 赞/ 154 阅读

相关最长公共子序列（LCS）

这两天编程涉及到求两个字符串的最长公共子序列问题，于是便重新复习之前一直没弄懂的最长公共子序列算法，也算是弄懂了一点。算法分析：采用动态规划方法来解决问题，将最长公共子

分手后的思念是犯贱/ 2022年09月29日 15:52/ 0 赞/ 154 阅读

相关最长公共子序列LCS问题

好久没有写博客了，刚才在网上看了清华大学的数据结构公开课，链接：https://www.xuetangx.com 可以注册个账号去听数据结构课程，老师讲的特好。我的代码是按

冷不防/ 2022年09月17日 15:21/ 0 赞/ 189 阅读

相关 LCS 最长公共子序列

首先要明白什么是子序列，什么是子串；设：主串长度为n；子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

绝地灬酷狼/ 2022年08月03日 14:57/ 0 赞/ 156 阅读

相关最长公共子序列(LCS)问题

> > 程序员编程艺术第十一章：最长公共子序列(LCS)问题 0、前言程序员编程艺术系列重新开始创作了（前十章，请参考[程序员编程艺术第一~十章集锦与总结][Li

你的名字/ 2022年07月12日 03:15/ 0 赞/ 164 阅读

相关最长公共子序列Lcs

1.给出两个字符串A B，求A与B的最长公共子序列的长度（子序列不要求是连续的）。 2.给出两个字符串A B，求A与B的最长公共子序列子串（子序列不要求是连续的）。

浅浅的花香味﹌/ 2022年06月12日 10:55/ 0 赞/ 167 阅读

相关最长公共子序列（LCS）算法

一、最长公共字串与最长公共子序列最长公共子串（Longest Common Substirng）子串是串的一个连续的部分，子串中字符的位置必须连续。例如：有

Love The Way You Lie/ 2022年06月05日 01:10/ 0 赞/ 234 阅读

相关求最长公共子序列（LCS）

题目：求最长公共子序列（LCS）思路：经典的动态规划法， c\[i,j\]表示Xi与Yj的最长公共子序列，其中 Xi = \{x1，、、、xi\}

傷城~/ 2022年05月30日 02:59/ 0 赞/ 183 阅读

相关【Python】最长公共子序列LCS

LCS的定义最长公共子序列，即Longest Common Subsequence，LCS。一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列；两

雨点打透心脏的1/2处/ 2022年05月22日 01:52/ 0 赞/ 193 阅读