定义：
1，一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列;
2，两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。
例：
字符串13455与245576的最长公共子序列为455
字符串acdfg与adfc的最长公共子序列为adf
3，注意区别最长公共子串(Longest Common Substring)
最长公共子串要求连续
字符串X，长度为m,从1开始数；
字符串Y，长度为n,从1开始数；
Xi 为字符串X的i前缀，
Yj为字符串Y的j前缀；
LCS(X,Y)为字符串X和Y的公共子序列集合。
LCS解法探索：
第一种情况： Xm = Yn;
若Xm = Yn(最后一个字符相同)
LCS(Xm, Yn) = LCS(Xm-1, Yn-1) + Xm;
这样我们解题的规模就减小了。
例：
LCS( BDC, ABC) = LCS( BD,AB) + ‘C‘
第二种情况：Xm != Yn
我们还是分类讨论:
如果Xm != Yn;
要么 LCS(Xm,Yn) = LCS(Xm-1,Yn); 丢弃Xm;
要么LCS(Xm,Yn) = LCS(Xm,Yn-1); 丢弃Yn;
这样我们只需求他们两个中最长的即可。
LCS(Xm,Yn) = max(LCS(Xm-1,Yn), LCS(Xm, Yn-1));
例：
LCS( BD,AB) = max(LCS(BD,A), LCS(B,AB));
这样我们可以得到：
LCS(Xm, Yn) = LCS(Xm-1,Yn-1) + Xm; 当Xm = Yn;
max( LCS(Xm-1), LCS(Xm,Yn-1) ); 当Xm != Yn;
显然，这就是动态规划问题
我们用一个二维数组chess[8][7]来表示：
X = "ABCBDAB"
Y = "BDCABA"
1,我们把第0行，第0列都初始化为0；表示和空串求最长子串，
2，我们比较X1（A） 和Y1（B）， 可以看到不相等，那么就调用max(LCS(X1，Y1))，X1 和 Y1 都为0，所以chess[x1][y1] = max(x1,y1) = 0
3，X1 != Y2, X1 != Y3, 所以都为0
4，当X1 == Y4== "A"时，我们调用相等时的式子，LCS(Xm,Yn) = LCS(Xm-1,Yn-1) + Xm; 所以chess[x1 = 1][Y4 = 4] = chess[x0 = 0][Y3 = 3] + 1;(相当于它的左上的值+1)
5， 当(X1 = A) != (Y5 = B)时，就是它的左边和上边的值求大者,max(0,1) = 1; 所以chess[1][5] = max(chess[1][4] + chess[0][5] ) = 1;
6,后面根据前面可以自己算出
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |||
| Yj | B | D | C | A | B | A | |||
| 0 | Xi | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | A | 0 | 0 | 0 | 0 | 1 | 1 | ||
| 2 | B | 0 | |||||||
| 3 | C | 0 | |||||||
| 4 | B | 0 | |||||||
| 5 | D | 0 | |||||||
| 6 | A | 0 | |||||||
| 7 | B | 0 |
完整的结果如下：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |||
| Yj | B | D | C | A | B | A | |||
| 0 | Xi | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | A | 0 | 0 | 0 | 0 | 1 | 1 | 1 | |
| 2 | B | 0 | 1 | 1 | 1 | 1 | 2 | 2 | |
| 3 | C | 0 | 1 | 1 | 2 | 2 | 2 | 2 | |
| 4 | B | 0 | 1 | 1 | 2 | 2 | 3 | 3 | |
| 5 | D | 0 | 1 | 2 | 2 | 2 | 3 | 3 | |
| 6 | A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | |
| 7 | B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
这样我们得到了最长的子串数目，但是我们应该如何表达呢？
我们从后面往前看，也就是绿色数字（ABCB）
最后我们在反转下就行了.(BCBA).
// // main.cpp // c++prime // // Created by SJCHEN on 2019/1/19. // Copyright © 2019 SJCHEN. All rights reserved. // #include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; void LCS(const char* a, const char*b, string &str) { int len1 = (int)strlen(a); int len2 = (int)strlen(b); const char* s1 = a - 1;//从1开始数 const char* s2 = b - 1; vector<vector<int>> chess(len1 + 1,vector<int>(len2+1));//二维数组 int i, j; for (i = 0; i <= len1; i++)//第0列 chess[i][0] = 0; for(j = 0; j <= len2; j++)//第0行 chess[0][j] = 0; for (i = 1; i <= len1; i++) { for (j = 1; j <= len2; j++) { if(s1[i] == s2[j]) chess[i][j] = chess[i-1][j-1] + 1; else chess[i][j] = max(chess[i][j-1], chess[i-1][j]); } } i = len1; j = len2; while (i != 0 && j != 0) { if (s1[i] == s2[j]) { str.push_back(s1[i]); i--; j--; } else { if (chess[i][j-1] > chess[i-1][j]) j--; else i--; } } reverse(str.begin(), str.end());//反转 } int main() { char *a,*b; string str; // cin >> a >> b; a = "ABCBDAB"; b = "BDCABA"; LCS(a,b,str); cout << str << endl; return 0; }
原文：https://www.cnblogs.com/SJCHEN/p/10573730.html