source code
https://github.com/haotang923/interview/tree/master/LCS
两个字符串求最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common Subsequence)的区别:子串要求在原字符串中是连续的,而子序列则只需保持相对顺序一致,并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1}。那么,{a, 1, 1}是X和Y的最长公共子序列,但不是它们的最长公共字串。
给定母串X=<x1,x2,⋯,xm>,Y=<y1,y2,⋯,yn>。
用二维数组c[i, j]记录结尾为xi与yj的子串的LCS长度,则最长公共子串状态转移方程如下
最长公共子串长度为max { c[i, j] }。
用二维数组c[i, j]记录串x1...xi与y1...yj的LCS长度,则最长公共子序列状态转移方程如下
最长公共子序列长度为c[m, n]。
注意代码中string下标从0开始,所以循环体内判断使用(str1[i - 1] == str2[j - 1])。
- 【动态规划】最长公共子序列与最长公共子串 - Treant - 博客园
- http://www.cnblogs.com/en-heng/p/3963803.html
- 【动态规划】Dynamic Programming - 神奕的专栏 - CSDN博客
- http://blog.csdn.net/lisonglisonglisong/article/details/41548557
- 【动态规划】输出所有的最长公共子序列 - 神奕的专栏 - CSDN博客
- http://blog.csdn.net/lisonglisonglisong/article/details/41596309
- 动态规划:求最长公共子串/最长公共子序列 - Sunshine的专栏 - CSDN博客
- http://blog.csdn.net/u013074465/article/details/45392687
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 // 2 // main.cpp 3 // LeetCode 4 // 5 // Created by Hao on 2017/3/16. 6 // Copyright © 2017年 Hao. All rights reserved. 7 // 8 9 #include10 #include 11 using namespace std;12 13 class Solution {14 public:15 int longestCommonSubstring(const string &str1, const string &str2) {16 vector< vector > f(str1.size() + 1, vector (str2.size() + 1) ); // 二维数组17 int result = 0;18 19 for (auto i = 0; i < str1.size() + 1; i ++) {20 for (auto j = 0; j < str2.size() + 1; j ++) {21 if (i == 0 || j == 0) // i == 0 or j == 022 f[i][j] = 0;23 else if (str1.at(i - 1) == str2.at(j - 1)) { // i, j > 0 and str1[i - 1] == str2[j - 1]24 f[i][j] = f[i - 1][j - 1] + 1;25 if (f[i][j] > result) result = f[i][j]; // 最长公共子串26 } else // i, j > 0 and str1[i - 1] != str2[j - 1], 区别于求最长公共子序列27 f[i][j] = 0;28 }29 }30 31 return result;32 }33 34 int longestCommonSubsequence(const string &str1, const string &str2) {35 vector< vector > f(str1.size() + 1, vector (str2.size() + 1) ); // 二维数组36 int result = 0;37 38 for (auto i = 0; i < str1.size() + 1; i ++) {39 for (auto j = 0; j < str2.size() + 1; j ++) {40 if (i == 0 || j == 0) // i == 0 or j == 041 f[i][j] = 0;42 else if (str1.at(i - 1) == str2.at(j - 1)) { // i, j > 0 and str1[i - 1] == str2[j - 1]43 f[i][j] = f[i - 1][j - 1] + 1;44 } else // i, j > 0 and str1[i - 1] != str2[j - 1], 区别于求最长公共子串45 f[i][j] = max(f[i][j - 1], f[i - 1][j]);46 }47 }48 49 // 矩阵最后一个元素50 result = f[str1.size()][str2.size()];51 52 return result;53 }54 };55 56 int main ()57 {58 Solution testSolution;59 60 vector vecTest1{ { "ABCBDAB"}, { ""}, { "ABC"}, { "ABC"} };61 vector vecTest2{ { "BDCABA"}, { ""}, { "DEF"}, { "ABC"} };62 63 for (auto i = 0; i < vecTest1.size(); i ++)64 cout << testSolution.longestCommonSubstring(vecTest1[i], vecTest2[i]) << endl;65 66 for (auto i = 0; i < vecTest1.size(); i ++)67 cout << testSolution.longestCommonSubsequence(vecTest1[i], vecTest2[i]) << endl;68 69 return 0;70 }