子序列
子序列不要求字符连续(这与串不同)
公共子序列
两个字符串中的相同的子序列
- 最大公共子序列的例子
字符串 X = sjdbfsb
字符串 Y = sdfsdf
LCS(X,Y) = sdf
算法
一些性质
字符串 最大公共子序列的长度
LCS[i][j]
则
- 如果
, 即两个字符串的最后一个字符相同, 这个字符一定属于LCS.所以
if(x[i] == y[j])
LCS[i][j] = LCS[i - 1][j - 1] + 1
- 如果
, 则产生两个问题 LCS(x,y,i,j-1),LCS(x,y,i-1,j),因为要求最大的子序列长度,取两者中较大的一个
- 如果i或j等于0,结果是0
代码
int* LCS = new int[i * j];
for(int m = 0; m < j; m++)
{
LCS[j] = 0;
}
for(int m = 0; m < i; m++)
{
LCS[m * i] = 0;
}
for(int m = 1; m < i; m++)
{
for(int n = 1; n < j; n++)
{
if(x[i] == y[j]
LCS[m * j + n] = LCS[(m - 1) * j + n-1] + 1;
else
LCS[m * j + n] = max(LCS[(m - 1) * j + n], LCS[m * j + n - 1]);
}
}
动态规划从底向上, 每个子问题只解决一次, 如果需要解决过的结果只需要 "查表", 比普通递归需要更多的空间
网友评论