本文共 2179 字,大约阅读时间需要 7 分钟。
参考:
一、求最长公共子序列
1、问题描述:
从一个给定的串中删去(不一定连续地删去)0个或0个以上的字符,剩下地字符按原来顺序组成的串。例如:“ ”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串“xaaabbb”的子序列。(例子中的串不包含引号。)
要求:给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
输入:输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。
输出:每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。
样例输入:
13456778 357486782样例输出:
51、暴力解法:
假设 m<n, 对于母串X,我们可以暴力找出2的m次方个子序列,然后依次在母串Y中匹配,算法的时间复杂度会达到指数级O(n∗2的m次)。显然,暴力求解不太适用于此类问题。2、递归求解:
当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。 在算法LCS中,每一次的递归调用使i或j减1,因此算法的计算时间为O(m+n)。3、动态规划:
(1)创建DP数组C[ ] [ ] (2)把首行和首列置零 (3)按照以下规则把表填满 C[8][9]=5即为所要求的最长公共子序列的长度代码如下:
#include#include int max(int a,int b){ return a>b?a:b;}int main(){ int i,j,k; char a[600]; char b[600]; int f[600][600]; while(scanf("%s %s",a,b)!=EOF) { int n=strlen(a); int m=strlen(b); for(i=0;i<=n;i++) { f[i][0]=0; } for(i=0;i<=m;i++) { f[0][i]=0; } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(a[i-1]==b[j-1]) { f[i][j]=f[i-1][j-1]+1; } else { f[i][j]=max(f[i-1][j],f[i][j-1]); } } } printf("%d\n",f[n][m]); } return 0;}
S1和S2的最LCS并不是只有1个,本文并不是着重讲输出两个序列的所有LCS,只是介绍如何通过上表,输出其中一个LCS。
我们根据递归公式构建了上表,我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。 c[8][9] = 5,且S1[8] != S2[9],所以倒推回去,c[8][9]的值来源于c[8][8]的值(因为c[8][8] > c[7][9])。 c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,c[8][8]的值来源于 c[7][7]。 以此类推,如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)第一种结果为:
这就是倒推回去的路径,棕色方格为相等元素,即LCS = {3,4,6,7,8},这是其中一个结果。如果如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,选择另一个方向,会得到另一个结果。
即LCS ={3,5,7,7,8}。二、DP求解最长公共子串
前面提到了子串是一种特殊的子序列,因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要,糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性,将二维数组c[i][j]用来记录具有这样特点的子串——结尾同时也为为串x1x2⋯xi与y1y2⋯yj的结尾——的长度。
得到转移方程: 最长公共子串的长度为 max(c[i,j]), i∈{1,⋯,m},j∈{1,⋯,n}。转载地址:https://blog.csdn.net/qq_43419016/article/details/89255931 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!