(完整word版)最长公共子序列长度算法

最长公共子序列（LCS）问题（非连续子序列）的两种解法最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。

其定义是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称S为已知序列的最长公共子序列。

关于子序列的定义通常有两种方式，一种是对子序列没有连续的要求，其子序列的定义就是原序列中删除若干元素后得到的序列。

另一种是对子序列有连续的要求，其子序列的定义是原序列中连续出现的若干个元素组成的序列。

求解子序列是非连续的最长公共子序列问题是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。

本文将介绍对子序列没有连续性要求的情况下如何用计算机解决最长公共子序列问题，对子序列有连续性要求的情况下如何用计算机解决最长公共子序列问题将在后续的文章中介绍。

一、动态规划法（Dynamic Programming）最长公共子序列问题应该是属于多阶段决策问题中求最优解一类的问题，凡此类问题在编制计算机程序时应优先考虑动态规划法，如果不能用动态规划法，而且也找不到其它解决方法，还可以考虑穷举法。

对于这个问题，只要能找到描述最长公共子序列的最优子结构和最优解的堆叠方式，并且保证最优子结构中的每一次最优决策都满足“无后效性”，就可以考虑用动态规划法。

使用动态规划法的关键是对问题进行分解，按照一定的规律分解成子问题（分解后的子问题还可以再分解，这是个递归的过程），通过对子问题的定义找出最优子结构中最优决策序列（对于子问题就是最有决策序列的子序列）以及最优决策序列子序列的递推关系（当然还包括递推关系的边界值）。

如果一个给定序列的子序列是在该序列中删去若干元素后得到的序列，也就意味着子序列在原序列中的位置索引（下标）保持严格递增的顺序。

例如,序列S = <B,C,D,B>是序列K = <A，B，C，B，D，A，B>的一个子序列（非连续），序列S的元素在在K中的位置索引I = [2,3,5,7]，I是一个严格递增序列。

试验四.最长公共子序列(LCS)算法一．实验原理对于给定的两个序列A和B，如果序列C既是A的子序列，又是B的子序列，则称C是A和B的公共子序列，A和B的公共子序列可能不止一个，其中最长的那个序列称为公共子序列。

公共子序列在很多实际应用中起关键作用。

序列A={abdledefiess},B={abwdifgdefiesa}，最长公共子序列为C={defies}二．实验目的本次实验就是要找出两个序列XY的最长公共子序列LCS三．实验步骤1.查找公共子序列2.输出公共子序列核心算法代码如下：int **lcs_length(char p[],char q[],int **c,int **k,int m,int n){int i,j;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(p[i-1]==q[j-1])//如果两个字母相等的情况{c[i][j]=c[i-1][j-1]+1;k[i][j]=1;}else{if(c[i-1][j]>=c[i][j-1])//两字母不等情况1{c[i][j]=c[i-1][j];k[i][j]=2;}else//两字母不等情况2{c[i][j]=c[i][j-1];k[i][j]=3;}}}}return c,k;}输出代码void print_lcs(int **k,char p[],int i,int j){if(i==0||j==0)return ;if(k[i][j]==1){print_lcs(k,p,i-1,j-1);//通过递归的方法按照输入的从头到尾的顺序输出LCScout<<p[i-1];}else if(k[i][j]==2)print_lcs(k,p,i-1,j);elseprint_lcs(k,p,i,j-1);}四.实验结果根据实验算法运行结果如下:以上算法表明可以正确的找出两个序列的最长公共子序列,达到了本次实验的目的.。

最长公共子序列算法最长公共子序列算法概述最长公共子序列（Longest Common Subsequence，LCS）是一种常见的字符串匹配问题。

给定两个字符串S和T，求它们的最长公共子序列，即在S和T中都出现的最长的子序列。

该问题可以用动态规划算法解决。

算法原理动态规划算法是一种将复杂问题分解成更小的子问题来解决的方法。

在LCS算法中，我们将两个字符串S和T分别看作X和Y，并定义一个二维数组c[i][j]表示X[1..i]和Y[1..j]的LCS长度。

则有以下递推公式：c[i][j] = 0, if i=0 or j=0c[i][j] = c[i-1][j-1]+1, if X[i]=Y[j]c[i][j] = max(c[i-1][j], c[i][j-1]), if X[i]!=Y[j]其中第一行和第一列均初始化为0，因为空字符串与任何字符串的LCS长度均为0。

当X[i]=Y[j]时，说明当前字符相同，那么当前字符可以加入到LCS中，所以LCS长度加1；否则当前字符不能加入到LCS中，则需要从上一个状态继承得到当前状态。

最终结果即为c[m][n]，其中m和n分别表示X和Y的长度。

算法实现以下是LCS算法的Python实现：def lcs(X, Y):m = len(X)n = len(Y)c = [[0] * (n+1) for i in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if X[i-1] == Y[j-1]:c[i][j] = c[i-1][j-1] + 1else:c[i][j] = max(c[i-1][j], c[i][j-1])return c[m][n]其中X和Y分别为两个字符串。

算法优化以上算法的时间复杂度为O(mn)，其中m和n分别表示X和Y的长度。

如果X和Y较长，算法会很慢。

但是我们可以通过一些优化来降低时间复杂度。

字符串最长公共子列算法问题：什么是字符串最长公共子列算法？字符串最长公共子列算法是一种用于寻找两个字符串中最长的共同子序列的算法。

一个子序列是指通过在原字符串中删除某些字符但不改变其余字符的顺序而得到的序列。

在字符串最长公共子列算法中，我们通过比较两个字符串的字符来确定它们之间的相似程度，并找到它们之间最长的相似子序列。

这个算法的应用非常广泛，尤其在文本搜索、数据压缩和生物信息学等领域。

在文本搜索方面，我们可以使用字符串最长公共子列算法来查找两个文本之间的相似性，从而确定它们之间的关联性。

在数据压缩方面，如果我们发现两个字符串中有很多相同的子序列，我们可以只存储这些相同的子序列，而不必重复存储它们，从而实现数据压缩的效果。

在生物信息学中，字符串最长公共子列算法可以用来比较两条DNA序列之间的相似性，从而找到它们之间的共同特征。

接下来，让我们具体了解字符串最长公共子列算法的实现步骤。

第一步：定义问题首先，我们需要明确这个问题的定义。

对于给定的两个字符串，我们需要找到它们之间的最长公共子序列的长度。

第二步：创建动态规划表格为了解决这个问题，我们可以使用动态规划的方法来构建一个二维表格。

表格的行表示第一个字符串的字符，列表示第二个字符串的字符。

表格的每个单元格表示当前位置的两个字符之间的最长公共子序列的长度。

第三步：填充表格我们从表格的第一个单元格开始填充。

如果两个字符相等，则该单元格的值等于左上方单元格的值加1。

如果两个字符不相等，则该单元格的值等于左方和上方两个单元格中较大的值。

我们按照从左到右、从上到下的顺序填充整个表格，直到最后一个单元格。

这样，我们就能够得到两个字符串之间的最长公共子序列的长度。

第四步：回溯寻找最长公共子序列通过遍历动态规划表格，我们可以回溯寻找最长公共子序列。

我们从表格的最后一个单元格开始，如果当前单元格的值与左方和上方单元格的值相等，说明该字符属于最长公共子序列中的一部分，我们就将该字符添加到结果序列中，并向左上方的单元格移动。

最长公共子序列GE GROUP system office room 【GEIHUA16H-GEIHUA GEIHUA8Q8-动态规划一、问题描述用动态规划法求两个字符串A=‘xzyzzyx’和B=‘zxyyzxz’的最长公共子序列二、算法分析(1)、若xm=yn,则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共自序列；(2)、若xm≠yn,且zk≠xm，则Zk是Xm-1和Yn的最长公共自序列；(3)、若xm≠yn,且zk≠yn，则Zk是Xm和Yn-1的最长公共自序列；设L(m,n)表示序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列的长度L表示已经决策的长度S表示每个决策的状态L(0,0)=L(0,j)=0 1≤i≤m, 1≤j≤nL(i-1,j-1)+1 xi=yi,i≥1,j≥1 L(i,j)=max{L(i,j-1),(L(i-1,j)} xi≠yi,i≥1,j≥1 1 xi=yiS(i,j)= 2 xi≠yi 且L(i,j-1)≥L(i-1,j)3 xi≠yi 且L(i,j-1)< L(i-1,j)长度矩阵L三、源代码#include <iostream>#include <string>using namespace std;int main(){string str1 = "xzyzzyx";string str2 = "zxyyzxz";int x_len = str1.length();int y_len = str2.length();int arr[50][50] ={{0,0}};int i = 0;int j = 0;for(i = 1; i <= x_len; i++){for(j = 1; j <= y_len; j++){if(str1[i - 1] == str2[j - 1]){arr[i][j] = arr[i - 1][j - 1] + 1;}else if(arr[i][j - 1] >= arr[i - 1][j]) arr[i][j] = arr[i][j - 1];elsearr[i][j] = arr[i -1][j];}}for(i = 0 ; i <= x_len; i++){for( j = 0; j <= y_len; j++){cout << arr[i][j] << " ";}cout << endl;}for(i = x_len, j = y_len; i >= 1 && j >= 1;) {if(str1[i - 1] == str2[j - 1]){cout << str1[i - 1] << " ";i--;j--;}else if(arr[i][j -1] > arr[i - 1][j]) j--;elsei--;}cout << endl;return 0;}。

利用递归求最长公共子序列问题1.引言最长公共子序列（Longest Common Subsequence，简称LCS）是一个经典的动态规划问题，其可以描述为：给定两个序列X和Y，求出它们的最长公共子序列的长度。

在计算机科学领域，LCS问题广泛应用于字符串比较、文本相似度计算、基因序列比对等领域，因此对于LCS问题的求解具有重要的意义。

2.问题描述对于序列X和Y，它们的最长公共子序列可以定义为：如果一个序列Z既是X的子序列又是Y的子序列，且Z的长度最大，那么Z称为X和Y的最长公共子序列。

3.递归解法我们可以使用递归的方式来解决LCS问题。

递归的思想是将原问题划分为更小的子问题求解，然后将子问题的解合并起来得到原问题的解。

对于LCS问题，我们可以将其划分为更小的子问题求解。

假设X和Y的长度分别为m和n，我们可以考虑X中的第m个元素和Y中的第n 个元素是否相等，从而将原问题划分为以下三种情况：a) 如果X[m]等于Y[n]，那么X和Y的最长公共子序列就是X[1..m-1]和Y[1..n-1]的最长公共子序列再加上X[m]。

b) 如果X[m]不等于Y[n]，那么X和Y的最长公共子序列就是X[1..m-1]和Y[1..n]的最长公共子序列，或者是X[1..m]和Y[1..n-1]的最长公共子序列，取两者的最大值。

c) 如果X或Y的长度为0，那么它们的最长公共子序列的长度为0。

4.递归求解步骤基于上述的划分情况，我们可以得到递归求解LCS问题的步骤如下：a) 如果X和Y的最后一个元素相等，那么LCS(X, Y, m, n) = 1 + LCS(X, Y, m-1, n-1)；b) 如果X和Y的最后一个元素不相等，那么LCS(X, Y, m, n) = max(LCS(X, Y, m-1, n), LCS(X, Y, m, n-1))；c) 如果m等于0或n等于0，那么LCS(X, Y, m, n) = 0。

// KSY.cpp : 定义控制台应用程序的入口点。

//#include "stdafx.h"#include <iostream>using namespace std;void LCSLength(intm,intn,char *x ,char *y, int **c, int **b) {inti ,j;for (i = 1; i<= m; i++) c[i][0] = 0;for (i = 1; i<= n; i++) c[0][i] = 0;for (i = 1; i<= m; i++)for (j = 1; j <= n; j++){if (x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if (c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}void LCS(inti ,int j, char *x ,int **b){if (i ==0 || j==0) return;if (b[i][j]== 1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}else if (b[i][j]== 2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);}constint M = 6;constint N = 5;void output(char *s,int n);void LCSLength(intm,intn,char *x,char *y,int * *c,int * *b); void LCS(inti,intj,char *x,int * *b);void main(){char x[] = {' ','B','C','E','F','G','T'};char y[] = {' ','C','D','F','J','G'};int **c = new int *[M+1];int **b = new int *[M+1];for(inti=0;i<=M;i++){c[i] = new int[N+1];b[i] = new int[N+1];}cout<<"序列X："<<endl;output(x,M);cout<<"序列Y："<<endl;output(y,N);LCSLength(M,N,x,y,c,b);cout<<"序列X、Y最长公共子序列长度为："<<c[M][N]<<endl; cout<<"序列X、Y最长公共子序列为："<<endl;LCS(M,N,x,b);cout<<endl;}void output(char *s,int n) {for(inti=1; i<=n; i++){cout<<s[i]<<" ";}cout<<endl;}。

动态规划经典——最长公共⼦序列问题（LCS）和最长公共⼦串问题⼀.最长公共⼦序列问题(LCS问题)给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共⼦序列，并返回其长度。

例如： A = "Hel lo W o rld" B = "loo p"则A与B的最长公共⼦序列为 "loo",返回的长度为3。

此处只给出动态规划的解法：定义⼦问题dp[i][j]为字符串A的第⼀个字符到第 i 个字符串和字符串B 的第⼀个字符到第 j 个字符的最长公共⼦序列，如A为“app”,B为“apple”，dp[2][3]表⽰ “ap” 和 “app” 的最长公共字串。

注意到代码中 dp 的⼤⼩为 (n + 1) x (m + 1) ，这多出来的⼀⾏和⼀列是第 0 ⾏和第 0 列，初始化为 0，表⽰空字符串和另⼀字符串的⼦串的最长公共⼦序列，例如dp[0][3]表⽰ "" 和“app” 的最长公共⼦串。

当我们要求dp[i][j]，我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同，如果相同它就是dp[i-1][j-1]+ 1，相当于在两个字符串都去掉⼀个字符时的最长公共⼦序列再加 1；否则最长公共⼦序列取dp[i][j - 1] 和dp[i - 1][j]中⼤者。

所以整个问题的初始状态为：dp[i][0]=0,dp[0][j]=0相应的状态转移⽅程为：dp[i][j]=max{dp[i−1][j],dp[i][j−1]},A[i−1]!=B[j−1] dp[i−1][j−1]+1,A[i−1]==B[j−1]代码的实现如下：class LCS{public:int findLCS(string A, int n, string B, int m){if(n == 0 || m == 0)//特殊输⼊return 0;int dp[n + 1][m + 1];//定义状态数组for(int i = 0 ; i <= n; i++)//初始状态dp[i][0] = 0;for(int i = 0; i <= m; i++)dp[0][i] = 0;for(int i = 1; i <= n; i++)for(int j = 1; j<= m; j++){if(A[i - 1] == B[j - 1])//判断A的第i个字符和B的第j个字符是否相同dp[i][j] = dp[i -1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}return dp[n][m];//最终的返回结果就是dp[n][m]}};该算法的时间复杂度为O(n*m)，空间复杂度为O(n*m)。

最长公共子序列（LCS）算法一．算法要求及分析1. 算法要求：利用b[i,j]，设计一个算法求出全部的LCS；利用”会计方法”，分析所编算法的时间复杂度的最坏情况。

2. 算法分析：该部分思路同课件二．算法详细设计为了求出全部的LCS,需要设计两个功能函数：LCS_L和LCS_Output，函数LCS_L实现计算LCS长度及每个子问题的由来；函数LCS_Output用递归方法实现输出所有LCS。

具体设计实现思路：1. 声明全局变量二维动态数组C和b。

数组C记录所要求的LCS的长度；数组b记录C[i,j]是通过哪一个子问题的值求得的。

定义枚举类型记录不同的遍历方向。

2. 用动态规划法实现功能函数LCS_L，得出数组C和b。

函数实现思路：首先动态分配和初始化二维数组C和b，然后计算出C和b。

根据X[i]和Y[j]的关系，计算得出C[i,j]：①若X[i]=Y[j]，则执行C[i,j]←C[i-1,j-1]+1且b[i][j]=ual；②若X[i]！=Y[j]，则分为三种情况：若C[i-1,j]>C[i,j-1]则C[i,j]取C[i-1,j]且b[i][j]=up;若C[i-1,j]<C[i,j-1]则C[i,j]取C[i,j-1]且b[i][j]=le;若C[i-1,j]=C[i,j-1]则C[i,j]取C[i-1,j]且b[i][j]=uol;3. 根据C和b编写输出函数LCS_Output输出所有的LCS。

函数实现思路：设置变量cur_len记录当前的数组下标，变量len保存当前LCS数组的元素个数。

依次扫描二维数组b，从最后一个开始，根据b的值来判断递归方向：当b的值是ual时，LCS数组保存当前字符，len++，沿对角线递归（递归完成要回溯）；len等于LCS的长度时即找到一个LCS序列并输出；当b的值是up时，向上递归；当b的值是le时，向左递归；当b的值是uol时，要找出所有的LCS，故既要向左也要向上递归。

最长公共子序列算法利用的算法最长公共子序列算法通常使用动态规划算法来实现。

动态规划是一种将问题拆分成子问题并按顺序解决的算法。

在最长公共子序列算法中，我们将两个序列分别称为序列X和序列Y。

我们定义一个二维数组dp，其中dp[i][j]表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度。

动态规划的递推关系如下：1. 如果X[i]等于Y[j]，则dp[i][j]等于dp[i-1][j-1]加1。

即序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度等于序列X的前i-1个元素和序列Y的前j-1个元素的最长公共子序列的长度加1。

2. 如果X[i]不等于Y[j]，则dp[i][j]等于dp[i-1][j]和dp[i][j-1]中的较大值。

即序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度等于序列X的前i-1个元素和序列Y的前j个元素的最长公共子序列的长度，或者序列X的前i个元素和序列Y的前j-1个元素的最长公共子序列的长度中的较大值。

通过填充dp数组，最终dp[X.length][Y.length]即为序列X和序列Y 的最长公共子序列的长度。

然后，我们可以通过回溯dp数组来找到最长公共子序列。

从dp[X.length][Y.length]开始，根据上述递推关系，如果dp[i][j]等于dp[i-1][j-1]加1，则说明X[i]等于Y[j]，将X[i]加入最长公共子序列中，并继续回溯dp[i-1][j-1]；如果dp[i][j]等于dp[i-1][j]，则说明X[i]不在最长公共子序列中，回溯dp[i-1][j]；如果dp[i][j]等于dp[i][j-1]，则说明Y[j]不在最长公共子序列中，回溯dp[i][j-1]。

最终，通过回溯，我们可以得到序列X和序列Y的最长公共子序列。

最长公共子序列长度
最长公共子序列长度是指两个序列中最长的公共子序列的长度。

公共子序列是指两个序列中都存在的、可能是不连续的相同元素组成的序列。

以下是一个计算最长公共子序列长度的动态规划算法：。

1. 定义一个二维数组dp，其中dp[i][j]表示序列1的前i个元素和序列2的前j个元素的最长公共子序列长度。

2. 初始化dp数组第一行和第一列。

dp[0][j]=0，dp[i][0]=0。

3. 递推计算剩余的dp数组。

当序列1的第i个元素等于序列2的第j个元素时，dp[i][j]=dp[i-1][j-1]+1，否则dp[i][j]=max(dp[i-
1][j],dp[i][j-1])。

4. 返回dp[m][n]，其中m和n分别为序列1和序列2的长度。

例如，对于序列1：ABCDABD和序列2：BDCABA，其最长公共子序列为BCBA，长度为4。

动态规划精选文库一、问题描绘用动向规划法求两个字符串A=‘ xzyzzyx ’和 B=‘ zxyyzxz ’的最长公共子序列二、算法剖析(1)、若 xm=yn, zk=xm=yn，且 Zk-1 是 Xm-1和 Yn-1 的最公共自序列；(2)、若 xm≠yn, 且 zk≠xm， Zk 是 Xm-1和 Yn的最公共自序列；(3)、若xm≠yn, 且zk≠yn，Zk 是Xm和Yn-1 的最公共自序列；L(m,n) 表示序列 X={x1,x2, ⋯,xm} 和 Y={y1,y2, ⋯,yn} 的最公共子序列的度L表示已决议的度S表示每个决议的状L(0,0)=L(0,j)=0 1≤i ≤m,1 ≤j ≤nL(i-1,j-1)+1xi=yi,i≥1,j≥1L(i,j)=max{L(i,j-1),(L(i-1,j)} xi≠yi,i ≥1,j≥11xi=yiS(i,j)= 2xi≠yi且L(i,j-1)≥L(i-1,j)精选文库3xi≠yi且L(i,j-1)< L(i-1,j)x z y z z y x00000000z00111111x01111222y01122222y01122333z01122334x01123334z01223344长度矩阵 L三、源代码#include <iostream>#include <string>using namespace std;int main(){string str1 = "xzyzzyx";string str2 = "zxyyzxz";精选文库int x_len = str1.length();int y_len = str2.length();int arr[50][50] ={{0,0}};int i = 0;int j = 0;for(i = 1; i <= x_len; i++){for(j = 1; j <= y_len; j++){if(str1[i - 1] == str2[j - 1]){arr[i][j] = arr[i - 1][j - 1] + 1;}else if(arr[i][j - 1] >= arr[i - 1][j])arr[i][j] = arr[i][j - 1];elsearr[i][j] = arr[i -1][j];}}精选文库for(i = 0 ; i <= x_len; i++){for( j = 0; j <= y_len; j++){cout << arr[i][j] << " ";}cout << endl;}for(i = x_len, j = y_len; i >= 1 && j >= 1;){if(str1[i - 1] == str2[j - 1]){cout << str1[i - 1] << " ";i--;j--;}else if(arr[i][j -1] > arr[i - 1][j])j--;elsei--;}cout << endl;精选文库return 0;}。

lrcs公式
LRCs公式是用于计算最长公共子序列（Longest Common Subsequence，LCS）的公式，可以用于衡量两个序列的相似度。

该公式将LCS长度分解为两个部分，即相干部分和非相干部分，相干部分对应于两个序列中的公共子序列，而非相干部分对应于两个序列中的不同部分。

具体来说，LRCs公式的计算公式如下：
LRCs = LCS(X, Y) + β2 PCS(X, Y)
其中，LCS(X, Y)表示X和Y的最长公共子序列长度，β为参数，PCS(X, Y)
表示X和Y的相干部分长度。

当β取值为无穷大时，相当于只考虑LCS(X, Y)。

另外，还有ROUGE-L的公式，用于评估机器翻译模型的性能。

该公式基于LRCs公式进行计算，具体如下：
ROUGE-L = (1 + β2) ROUGE-L P / (β2 P + ROUGE-L P)
其中，ROUGE-L P表示模型生成的摘要与参考摘要之间的最长公共子序列长度，β为参数，P表示参考摘要中单词的个数。

当β取值为无穷大时，相当于只考虑ROUGE-L P。

算法系列之六：最长公共子序列（LCS）问题（连续子序列）的三种解法最长公共子序列（LCS）问题有两种方式定义子序列，一种是子序列不要求不连续，一种是子序列必须连续。

上一章介绍了用两种算法解决子序列不要求连续的最终公共子序列问题，本章将介绍要求子序列必须是连续的情况下如何用算法解决最长公共子序列问题。

仍以上一章的两个字符串“abcdea”和“aebcda”为例，如果子序列不要求连续，其最长公共子序列为“abcda”，如果子序列要求是连续，则其最长公共子序列应为“bcd”。

在这种情况下，有可能两个字符串出现多个长度相同的公共子串，比如“askdfiryetd”和“trkdffirey”两个字符串就存在两个长度为3的公共子串，分别是“kdf”和“fir”，因此问题的性质发生了变化，需要找出两个字符串所有可能存在公共子串的情况，然后取最长的一个，如果有多个最长的公共子串，只取其中一个即可。

字符串“abcdea”和“aebcda”如果都以最左端的a字符对齐，则能够匹配的最长公共子串就是“a”。

但是如果用第二个字符串的e字符对齐第一个字符串的a 字符，则能够匹配的最长公共子串就是“bcd”。

可见，从两个字符串的不同位置开始对齐匹配，可以得到不同的结果，因此，本文采用的算法就是穷举两个字符串所有可能的对齐方式，对每种对齐方式进行字符的逐个匹配，找出最长的匹配子串。

一、递归方法首先看看递归方法。

递归的方法比较简单，就是比较两个字符串的首字符是否相等，如果相等则将其添加到已知的公共子串结尾，然后对两个字符串去掉首字符后剩下的子串继续递归匹配。

如果两个字符串的首字符不相等，则用三种对齐策略分别计算可能的最长公共子串，然后取最长的一个与当前已知的最长公共子串比较，如果比当前已知的最长公共子串长就用计算出的最长公共子串代替当前已知的最长公共子串。

第一种策略是将第一个字符串的首字符删除，将剩下的子串与第二个字符串继续匹配；第二种策略是将第二个字符串的首字符删除，将剩下的子串与第一个字符串继续匹配；第三种策略是将两个字符串的首字符都删除，然后继续匹配两个字符串剩下的子串。

求连续的最长公共子串•首先我们来分析一个简单例子。

•LCS(‘212325233’,’312123223’)=‘21232’•我们看是如何求解出来的,如下图,红色下划线表示已匹配。

分析•从前面例子可以看出解题思路：•每次都是将子串的每一位与母串的每一位比较，然后根据比较的结果找LCS。

因此，我们需要借助一个二维数组存储两个串比较后的结果，用１表示匹配成功，０表示不成功。

如匹配结果如下图(1),最长公共子串见图(2)。

进一步分析•在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。

通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。

下面是新的矩阵生成方式：算法•设置一个矩阵，记录两个串的匹配情况。

•当字符匹配的时候，不是简单的给相应元素赋上1，而是赋上其左上角元素的值加１。

•我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断•当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

•显然该算法的时间复杂度为两个串的长度乘积。

for(i=1;i<=row;i++) {for(j=1;j<=col;j++) {if(s[i-1]==rs[j-1]) {lcs[i][j]=lcs[i-1][j-1]+1;}else{if(lcs[i-1][j]>=lcs[i][j-1]) {lcs[i][j]=lcs[i-1][j];}else {lcs[i][j] = lcs[i][j-1];}}}}return lcs[row][col];}。

10031003 Common SubsequenceA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another sequence Z = is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = is a subsequence of X = with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.Sample Inputabcfbc abfcabprogramming contestabcd mnpSample Output42C++语言: Codee#895801#include <cstdlib>02#include <iostream>03using namespace std;04#define N 10505int dp[N+1][N+1] ;06char str1[N] , str2[N];07int maxx(int a , int b)08 {09if(a > b)10return a ;11return b ;12 }13int LCSL(int len1 , int len2)14 {15int i , j ;16int len = maxx(len1 , len2);17for( i = 0 ; i <= len; i++ )18{19dp[i][0] = 0 ;dp[0][i] = 0 ;20}21for( i = 1 ; i<= len1 ; i++)22for( j = 1 ; j <= len2 ; j++)2324{25if(str1[i - 1] == str2[j - 1])26{27dp[i][j] = dp[i - 1][ j - 1] + 1 ;28}29else30{31dp[i][j] = maxx(dp[i - 1][ j ] , dp[i][j - 1]) ; 32}33}34return dp[len1][len2];35 }36int main()37 {38while(cin >> str1 >> str2)3940{41int len1 = strlen(str1) ;42int len2 = strlen(str2) ;43cout<<LCSL(len1 , len2)<<endl;44}45return0;46 }一、最长公共子序列(Longest Common Subsequence:LCS)设有两个序列A[1...m]和B[1...n],分别对A和B进行划分子序列A[1] A[1..2] A[1..3] ... A[1..m]B[1] B[1..2] B[1..3] ... B[1..n]依次求出A中的每个子序列(从A[1]开始)与B中每个子序列的最长公共子序列，并记录在数组C[m][n]中，C[i][j]表示A[1..i]和B[1..j]的最长公共子序列的长度。

最长公共子序列1题目分析两个序列的最长公共子序列的长度为最优值，利用动态规划法2算法构造引入二维数组C[i,j]记录Xi = < xl,x2 , … , xi>和Yj =二< y1 ;y2 , ,…, yj > 根据子问题最优值的递归关系，可自底向上建立递推关系如下：当 i = 0 , j = 0 时 , c[i][j] = 0当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }3算法实现#include <iostream>#include <string>using namespace std;//计算最优值void LCSLength(int m,int n,char *y,char *x,int **c,int **b){int i,j;for(i=1;i<=m;i++)c[i][0]=0;for(j=0;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else {c[i][j]=c[i][j-1];b[i][j]=3;}}}//构造最长公共子序列void LCS(int i,int j,char *x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}else if(b[i][j]==2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);}//主函数int main(){int m,n;char *x,*y;int **b,**c;void LCSLength(int m,int n,char *y,char *x,int **c,int **b);void LCS(int i,int j,char *x,int**b);cout<<"请输入两个序列的长度："<<endl;cin>>m>>n;x=new char[m];y=new char[n];cout<<"请输入两个序列："<<endl;cin>>x>>y;b=new int *[m + 1];for (int i=0;i<=m;i++)b[i]=new int[n + 1];c=new int *[m + 1];for (int j=0;j<=m;j++)c[j]=new int[n + 1];LCSLength(m,n,x,y,c,b);cout<<"最长公共子序列的元素个数为"<<c[m][n]<<endl;cout<<"该序列为:";LCS(m,n,x,b);cout<<endl;return 0;}4运行结果请输入两个序列的长度：55请输入两个序列：dfdhhdfdgh最长公共子序列的元素个数为4该序列为:dfdhPress any key to continue。

动态规划问题描述用动态规划法求两个字符串A= ' xzyzzyx '和B= ' zxyyzxz '的最长公共子序列二、算法分析(1)、若xm=yn,贝卩zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共自序列；⑵、若xm^yn,且zk工xm,则Zk是Xm-1和Yn的最长公共自序列；⑶、若xm^yn,且zk工yn，则Zk是Xm和Yn-1的最长公共自序列；设L(m,n)表示序列X=｛x1,x2,…,xm｝和Y二｛y1,y2,…,yn｝的最长公共子序列的长度L表示已经决策的长度S表示每个决策的状态L(O,O)=L(O,j)=O 1 < i < m, 1 < j < nL(i-1/-1)+1 xi=yi,i > 1,j > 1L(i,j)=max{L(i,j-1),(L(i-1,j)} xi工yi,i > 1,j > 11 xi=yi工yi 且L(i,j-1) > L(i-1,j)工yi 且L(i,j-1)< L(i-1,j)长度矩阵L三、源代码#in elude <iostream>#in elude <stri ng>using n amespaee std;int mai n(){stri ng strl = "xzyzzyx";stri ng str2 = "zxyyzxz";int x_le n 二 strl.le ngth(); int y_le n = str2 .len gth();int arr[50][50] ={{0,0}};int i = 0;int j = 0;for(i = 1; i <= x_len; i++){for(j = 1; j <= y_len; j++){if(str1[i - 1] == str2[j - 1]){arr[i][j] = arr[i - 1][j - 1] + 1;}else if(arr[i][j - 1] >= arr[i - 1][j]) arr[i][j] = arr[i][j -1];elsearr[i][j] = arr[i -1][j];}}for(i = 0 ; i <= x_len; i++){for( j = 0; j <= y_len; j++){cout << arr[i][j] << " ";}cout << endl;}for(i = x_len, j = y_len; i >= 1 && j >= 1;) { if(str1[i - 1] == str2[j - 1]){cout << str1[i - 1] << " ";i--;j--;}else if(arr[i][j -1] > arr[i - 1][j])j--;elsei--;}cout << endl;return 0;}。