生活随笔
收集整理的这篇文章主要介绍了
算法：最长公共子序列（输出所有最长公共子序列）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
问题描述：给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的最长公共子序列的长度。
下面是求解时的动态规划表，可以看出 X 和 Y 的最长公共子序列的长度为4：
输出一个最长公共子序列并不难（网上很多相关代码），难点在于输出所有的最长公共子序列，因为 LCS 通常不唯一。
我们需要在动态规划表上进行回溯 —— 从c
[m
][n
]，即右下角的格子，开始进行判断：如果格子c
[i
][j
]对应的X
[i-1
] == Y
[j-1
]，则把这个字符放入 LCS 中，并跳入c
[i-1
][j-1
]中继续进行判断；如果格子c
[i
][j
]对应的 X
[i-1
] ≠ Y
[j-1
]，则比较c
[i-1
][j
]和c
[i
][j-1
]的值，跳入值较大的格子继续进行判断；如果出现c
[i-1
][j
]等于c
[i
][j-1
]的情况，说明最长公共子序列有多个，故两边都要进行回溯（这里用到递归）。直到 i 或 j 小于等于零为止，倒序输出 LCS 。
从上图的红色路径显示，X 和 Y 的最长公共子序列有 3 个，分别为 “BDAB”、“BCAB”、“BCBA”。
C++代码：
#include<bits/stdc++.h>
using namespace std
;string X
;
string Y
;
vector
<vector
<int> > c
;
set
<string
> lcs
; int lcs_length(int m
, int n
)
{c
= vector
<vector
<int> >(m
+1,vector
<int>(n
+1));for(int i
=0; i
<m
+1; ++i
){for(int j
=0; j
<n
+1; ++j
){if (i
== 0 || j
== 0)c
[i
][j
] = 0;else if(X
[i
-1] == Y
[j
-1])c
[i
][j
] = c
[i
-1][j
-1] + 1;elsec
[i
][j
] = max(c
[i
-1][j
], c
[i
][j
-1]);}}return c
[m
][n
];
}void lcs_print(int i
, int j
, string lcs_str
)
{while (i
>0 && j
>0){if (X
[i
-1] == Y
[j
-1]){lcs_str
.push_back(X
[i
-1]);
--i
;--j
;}else{if (c
[i
-1][j
] > c
[i
][j
-1])--i
;else if (c
[i
-1][j
] < c
[i
][j
-1])--j
;else{lcs_print(i
-1, j
, lcs_str
);lcs_print(i
, j
-1, lcs_str
);return;}}}
reverse(lcs_str
.begin(),lcs_str
.end());lcs
.insert(lcs_str
);
}int main()
{cin
>>X
>>Y
;int m
= X
.length();int n
= Y
.length();int length
= lcs_length(m
, n
);cout
<< "The length of LCS is " << length
<< endl
;string str
;lcs_print(m
, n
, str
);set
<string
>::iterator it
= lcs
.begin();for( ; it
!=lcs
.end(); it
++)cout
<< *it
<< endl
;return 0;
}
运行效果：
总结
以上是生活随笔为你收集整理的算法：最长公共子序列（输出所有最长公共子序列）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
