做的网站怎么放到网上,达内网站建设,修改散文网站,天宁区建设局网站问题介绍
LCS问题(longest common subsequence problem)指的是求解两个字符串最长公共子序列问题。这里的子序列是可以不连续的。LCS问题广泛地出现在计算生物学中#xff08;DNA序列、系统生成树等等#xff09;。这里介绍如何解决LCS问题#xff0c;以及算法的正确性证明…问题介绍
LCS问题(longest common subsequence problem)指的是求解两个字符串最长公共子序列问题。这里的子序列是可以不连续的。LCS问题广泛地出现在计算生物学中DNA序列、系统生成树等等。这里介绍如何解决LCS问题以及算法的正确性证明和性能分析。
解决方案
假设需要求解串X,Y的LCS其中|X|n,|Y|m,c[i][j]表示X[1…i]和Y[1…j]的LCS长度,z[1…k]表示X[1…i]和Y[1…j]的LCS,kc[i][j]则问题就是求解c[n][m]和z[c[n][m]]c[n][m]和z[c[n][m]]c[n][m]和z[c[n][m]]
朴素的想法是按照问题的要求我们可以得到串X的所有子串共有2n2^n2n个然后判断该子串是否出现在串Y中每次判断都需要遍历串Y因此时间复杂度为O(2n∗m)O(2^n*m)O(2n∗m)这显然是我们不能接受的复杂度。
为了解决这个问题我们需要得到该问题的一些性质
定理:
ifX[i]Y[j]:c[i][j]c[i−1][j−1]1if X[i]Y[j]:c[i][j]c[i-1][j-1]1 ifX[i]Y[j]:c[i][j]c[i−1][j−1]1
otherwisec[i][j]max(c[i−1][j],c[i][j−1])otherwisec[i][j]max(c[i-1][j],c[i][j-1]) otherwisec[i][j]max(c[i−1][j],c[i][j−1])
引理1:如果X[i]Y[j]则z[c[i][j]]X[i]z[c[i][j]]X[i]z[c[i][j]]X[i]
证明如果z[c[i][j]]≠X[i]z[c[i][j]]\neq X[i]z[c[i][j]]X[i]且X[i]Y[j]那么不妨将X[i]加入到LCS中c[i][j]c[i][j]c[i][j]加一因此z[1..c[i][j]]z[1..c[i][j]]z[1..c[i][j]]不是LCS与条件矛盾证毕。
引理2:如果X[i]Y[j]则X[i-1]和Y[j-1]的LCS是z[1..c[i][j]−1]z[1..c[i][j]-1]z[1..c[i][j]−1]
证明X[i-1]和Y[j-1]的LCS不是z[1..c[i][j]−1]z[1..c[i][j]-1]z[1..c[i][j]−1]则使用X[i-1]和Y[j-1]的LCS替换z[1..c[i][j]−1]z[1..c[i][j]-1]z[1..c[i][j]−1]后再加上X[i]会得到X[i]和Y[j]的一个更长的一个LCS与条件矛盾证毕。引理2这里展示了问题的最优子结构
引理3:如果两个串的LCS包含两个串的末尾元素X[i]和Y[j]则这两个元素相等
证明如果X[i]不等于Y[j]则在LCS中X[i]对应Y[j’],j’jY[j]对应X[i’],i’i这不符合公共子串保留原串顺序的性质矛盾。证毕。
当X[i]Y[j]时由引理1保证了此时的LCS是串X[i]对应串Y[j’],j′⩽jj\leqslant jj′⩽j对于j′jj jj′j的情况我们不妨用jjj来替换j′jj′这样也不会对LCS的长度有什么影响然后由引理2c[i][j]c[i−1][j−1]1c[i][j]c[i-1][j-1]1c[i][j]c[i−1][j−1]1
对于第二个条件因为X[i]≠\neqY[j]那么此时的LCS要么属于c[i−1][j]c[i-1][j]c[i−1][j]要么属于c[i][j−1]c[i][j-1]c[i][j−1]。
假设都不属于那么此时的LCS一定包含了c[i−1][j]c[i-1][j]c[i−1][j]中没有的元素X[i]和c[i][j−1]c[i][j-1]c[i][j−1]中没有的元素Y[j]由引理3矛盾。
在证明了上述定理以后我们可以根据该式子计算LCS:
递归法
int LCS(string x, string y,int n,int m)
{if(-1n || -1m) return 0;if(x[n]y[m]) return LCS(x, y, n-1, m-1)1;else return max(LCS(x, y, n-1, m), LCS(x, y, n, m-1));
}
性能分析
分析递归树最坏的情况是每次x[n]!y[m]那么会得到一个高度为nm的二叉树时间复杂度为O(2nm)O(2^{nm})O(2nm)空间复杂度为O(nm)O(nm)O(nm)
备忘录方法记忆化搜索
分析上面时间复杂度我们发现在搜索过程中很多的子问题都是一模一样的也就是具有重叠子问题性质因此我们不妨每计算出一个子问题的结果就进行一次记录后面再次需要求解结果的时候就不需要再计算而是直接返回结果。
int LCS(string x, string y,int n,int m,int *c)
{if(-1n || -1m) return 0;if(c[n*y.size()m]) return c[n*y.size()m];int ret;if(x[n]y[m]) ret LCS(x, y, n-1, m-1, c)1;else ret max(LCS(x, y, n-1, m, c), LCS(x, y, n, m-1, c));return c[n*y.size()m]ret;
}int main()
{string X,Y;cout请输入字符串X:; cinX;cout请输入字符串Y:; cinY;int* c new int[X.size()*Y.size()10]();cout字符串X和Y的LCS的长度为LCS(X, Y, X.size(), Y.size(), c)endl;delete c;return 0;
}性能分析
我们可以把对结果是否已经计算出的判断和返回答案的耗费记录在调用该状态答案的耗费上把实际结果的计算记录在该状态中则最坏情况下每种状态都要计算出来因此时间复杂度为O(nm)O(nm)O(nm)空间复杂度为O(nm)O(nm)O(nm)
自底向上计算动态规划法
我们观察计算的过程如果我们对状态空间按照从左向右从上向下进行求解就可以计算出所有的答案
int LCS(string x, string y,int n,int m,int *c)
{for(int i1; ix.size(); i){for(int j1;jy.size(); j){if(x[i-1] y[j-1])c[i*y.size()j]c[(i-1)*y.size()j-1]1;elsec[i*y.size()j]max(c[(i-1)*y.size()j], c[(i)*y.size()j-1]);}}return c[n*y.size()m];
}
性能分析
时间复杂度O(nm)O(nm)O(nm)因为访问的是连续的内存空间因此这里的O(nm)O(nm)O(nm)应该比上面小。空间复杂度O(nm)O(nm)O(nm)如果使用滚动数组还能够将空间复杂度降低为O(min(n,m))O(min(n,m))O(min(n,m))如果不使用滚动数组想要得到完整的LCS串需要在计算的时候设置指针最后进行回溯。如果使用滚动数组需要使用分治法得到LCS串。
回溯如图
