公共子序列:我们称序列 Z = <z1, z2, …, zk> 是序列 X = <x1, x2, …, xm> 的子序列当且仅当存在 严格上升 的序列 <i1, i2, …, ik>,使得对 j = 1, 2, … ,k, 有 xij = zj。比如 Z = <a, b, f, c> 是 X = <a, b, c, f, b, c> 的子序列。
现在给出两个序列 X 和 Y,你的任务是找到 X 和 Y 的最大公共子序列,也就是说要找到一个最长的序列 Z,使得 Z 既是 X 的子序列也是 Y 的子序列。输入输入包括多组测试数据。每组数据包括一行,给出两个长度不超过 200 的字符串,表示两个序列。两个字符串之间由若干个空格隔开。输出对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。样例输入 abcfbc abfcabprogramming contestabcd mnp 样例输出 420
maxLens1 左边 i 个字符子串,s2 左边的 j 个字符子串的最长公共子序列递推公式:if(s1[i-1]==s2[j-1])maxLen(i,j)=maxLen(i-1,j-1)+1elsemaxLen(i,j)=max(maxLen(i,j-1),maxLen(i-1,j))
- #includeusing namespace std;
- char s1[1000];
- char s2[1000];
- int maxLEN[1000][1000];
- int main() {
- while (cin >> s1 >> s2) {
- int length1 = strlen(s1);
- int length2 = strlen(s2);
- int temp;
- int i,
- j;
- for (i = 0; i <= length1; i++) {
- maxLEN[i][0] = 0;
- }
- for (j = 0; j <= length2; j++) {
- maxLEN[0][j] = 0;
- }
- for (i = 1; i <= length1; i++) {
- for (j = 1; j <= length2; j++) {
- if (s1[i - 1] == s2[j - 1]) maxLEN[i][j] = maxLEN[i - 1][j - 1] + 1;
- else maxLEN[i][j] = max(maxLEN[i][j - 1], maxLEN[i - 1][j]);
- }
- }
- cout <
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-17/20572792.html