# 最長公共子序列和最長公共子串區別
????? 最長公共子串（Longest Common Substring）與最長公共子序列（Longest Common Subsequence）的區別： 子串要求在原字符串中是連續的，而子序列則只需保持相對順序一致，并不要求連續。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最長公共子序列，但不是它們的最長公共字串。
# 一、最長公共子序列
具體的算法思想參考以下文章：
[http://blog.csdn.net/lisonglisonglisong/article/details/41548557](http://blog.csdn.net/lisonglisonglisong/article/details/41548557)
[http://blog.csdn.net/zhongkeli/article/details/8847694](http://blog.csdn.net/zhongkeli/article/details/8847694)
[
](http://blog.csdn.net/zhongkeli/article/details/8847694)
### 只求最長子序列長度
如果僅僅需要知道最長子序列的長度值，代碼如下：
~~~
#include <vector>
#include <string>
#include <iostream>
#include <string.h>
#include <sstream>
using namespace std;
//最長公共子串（LCS）
//二維數組veca記錄的是兩個字符串Xi和Yj的LCS長度
int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i][0] = 0;
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
}
else {
if (veca[i - 1][j] >= veca[i][j - 1])
veca[i][j] = veca[i - 1][j];
else
veca[i][j] = veca[i][j-1];
}
}
}
return veca[str1.length()][str2.length()];
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1, str2;
ss >> str1;
ss >> str2;
//將veca初始化為一個二維數組,其行列值分別為str1和str2的長度加1
//二維數組veca記錄的是兩個字符串Xi和Yj的LCS長度
vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
cout << LCS_length(str1, str2, veca) << endl;
return 0;
}
~~~
結果：
動態規劃解決LCS問題的時間復雜度為O(mn)，這比簡單的遞歸實現要快多了。空間復雜度是O(mn)，因為使用了一個動態規劃表。
### 要輸出一個LCS的內容
和上面的程序比，只需要多一個二維數組記錄在遍歷中所選擇的子問題的最優解即可。如下程序：
~~~
//輸出最長公共子串（LCS）
//二維數組veca記錄的是兩個字符串Xi和Yj的LCS長度
int LCS_length(const string &str1, const string &str2,
vector<vector<int> > &veca, vector<vector<int> > &vecb) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i][0] = 0;
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
//如果Xi-1 == Yj-1，那么最長子序列為veca[i - 1][j - 1] + 1
//此時將vecb[i][j] = 1表明str1[i-1]是子問題LCS的一個元素
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
vecb[i][j] = 1;
}
else {
if (veca[i - 1][j] >= veca[i][j - 1]) {
veca[i][j] = veca[i - 1][j];
vecb[i][j] = 2;
}
else {
veca[i][j] = veca[i][j-1];
vecb[i][j] = 3;
}
}
}
}
return veca[str1.length()][str2.length()];
}
//該函數用于輸出一個LCS的序列
//這里輸出的順序是先向上尋找，再向左尋找
void PrintOneLCS(vector<vector<int> > &vecb, string &str1, int i, int j) {
if (i == 0 || j == 0)
return;
if (vecb[i][j] == 1) {
PrintOneLCS(vecb, str1, i - 1, j - 1);
cout << str1[i - 1] << " ";
}
else if (vecb[i][j] == 2)
PrintOneLCS(vecb, str1, i -1, j);
else
PrintOneLCS(vecb, str1, i, j - 1);
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1, str2;
ss >> str1;
ss >> str2;
//將veca初始化為一個二維數組,其行列值分別為str1和str2的長度加1
//二維數組veca記錄的是兩個字符串Xi和Yj的LCS長度
//二維數組vecb[i][j]記錄veca[i][j]時所選擇的子問題的最優解
vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
vector<vector<int> > vecb(str1.length() + 1, vector<int>(str2.length() + 1));
cout << LCS_length(str1, str2, veca, vecb) << endl;
PrintOneLCS(vecb, str1, str1.length(), str2.length());
return 0;
}
~~~
求一個LCS內容也可以不借助輔助二維數組vecb而是用下面小節的方法，
~~~
//該函數用于輸出一個LCS的序列，使用下一小節的方法
//這里輸出的順序是先向左尋找，再向上尋找
void PrintOneLCS(string &str1, string &str2, int i, int j,
vector<vector<int> > &veca) {
string lcs_str;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs_str = str1[i - 1] + lcs_str;
--i;
--j;
}
else {
//如果左邊存在LCS就從左邊找否則再從右邊找
if (veca[i - 1][j] >= veca[i][j - 1])
--i;
else
--j;
}
}
cout << lcs_str << endl;
}
~~~
如下代碼：
### 要輸出所有LCS的內容
兩個字符串對應的最長公共子序列不一定唯一，這個程序輸出所有的LCS內容。
基本思想是：
具體參考文章：[http://blog.csdn.net/lisonglisonglisong/article/details/41596309](http://blog.csdn.net/lisonglisonglisong/article/details/41596309)
代碼：
~~~
#include <vector>
#include <iomanip>
#include <set>
#include <string>
#include <map>
#include <iostream>
#include <string.h>
#include <sstream>
using namespace std;
set<string> all_lcs; //注意這里要用set去除重復的LCS
//最長公共子串（LCS）
//二維數組veca[i][j]記錄的是兩個字符串Xi和Yj的LCS長度
int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i][0] = 0;
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
}
else {
if (veca[i - 1][j] >= veca[i][j - 1])
veca[i][j] = veca[i - 1][j];
else
veca[i][j] = veca[i][j-1];
}
}
}
return veca[str1.length()][str2.length()];
}
//該函數找出所有的LCS的序列，并將其存在vector中
void PrintAllLCS(string &str1, string &str2, int i, int j,
vector<vector<int> > &veca, string lcs_str) {
//注意這里形參lcs_str不可以為引用，這里需要每次調用lcs_str都重新生成一個對象
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs_str = str1[i - 1] + lcs_str; //逆向存放
--i;
--j;
}
else {
if (veca[i - 1][j] > veca[i][j - 1]) //向左走
--i;
else if (veca[i - 1][j] < veca[i][j - 1]) //向上走
--j;
else { //此時向上向右均為LCS的元素
PrintAllLCS(str1, str2, i - 1, j, veca, lcs_str);
PrintAllLCS(str1, str2, i, j - 1, veca, lcs_str);
return;
}
}
}
cout << " " << lcs_str << endl;
all_lcs.insert(lcs_str);
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1, str2;
ss >> str1;
ss >> str2;
//將veca初始化為一個二維數組,其行列值分別為str1和str2的長度加1
//二維數組veca記錄的是兩個字符串Xi和Yj的LCS長度
vector<vector<int> > veca(str1.length() + 1, vector<int>(str2.length() + 1));
cout << LCS_length(str1, str2, veca) << endl;
string lcs_str;
PrintAllLCS(str1, str2, str1.length(), str2.length(), veca, lcs_str);
set<string>::iterator iter = all_lcs.begin();
while (iter != all_lcs.end()) {
cout << *iter++ << endl;
}
return 0;
}
~~~
如圖所示的兩個字符串共有三個LCS。
# 二、最長公共子串
**描述：**
計算兩個字符串的最大公共子串（Longest Common Substring）的長度，字符不區分大小寫。
**輸入：**
輸入兩個字符串
**輸出：**
輸出一個整數
**樣例輸入：**
~~~
asdfas werasdfaswer
~~~
**樣例輸出：**
~~~
6
~~~
這里的**最大公共字串要求的字串是連續**的。
求字串的方法和求子序列方法類似：
當str1[i] == str2[j]時，子序列長度veca[i][j] = veca[i - 1][j - 1] + 1；只是當str1[i] ！= str2[j]時，veca[i][j]長度要為0，而不是max{veca[i - 1][j], veca[i][j - 1]}。
~~~
#include <vector>
#include <string>
#include <iostream>
#include <string.h>
#include <sstream>
using namespace std;
int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {
int i, j;
int biggest = 0;
if (str1 == "" || str2 == "")
return 0;
for (i = 0; i <= str1.length(); i++) {
veca[i].resize(str2.length() + 1, 0);
}
for (j = 0; j <= str2.length(); j++) {
veca[0][j] = 0;
}
for (i = 1; i <= str1.length(); i++) {
for (j = 1; j <= str2.length(); j++) {
if (str1[i - 1] == str2[j - 1]) {
veca[i][j] = veca[i - 1][j - 1] + 1;
if (veca[i][j] > biggest)
biggest = veca[i][j];
}
else
//可以看出，求最長子串和求最長子序列差別僅僅在這里
veca[i][j] = 0;
}
}
return biggest;
}
int main() {
string input;
getline(cin, input);
stringstream ss(input);
string str1;
ss >> str1;
string str2;
ss >> str2;
vector<vector<int> > veca(str1.length() + 1);
cout << LCS_length(str1, str2, veca) << endl;
return 0;
}
~~~
同樣適用求最長子序列的測試數據，得到它們的公共最長子串長度為2，而它們的公共最長子序列長度為4.
# 三、動態規劃的其它題目
1、硬幣面值組合問題
[http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html](http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html)
2、[最長遞增子序列](http://blog.csdn.net/u013074465/article/details/45442067)
? ? ? ? ?除了動態規劃，該題還有其他解法。
3、數組最大子數組和的最大值
[http://www.ahathinking.com/archives/120.html](http://www.ahathinking.com/archives/120.html)
3、[動態規劃之鋼條分割](http://blog.csdn.net/u013074465/article/details/44920979)
4、計算兩個字符串的相似度（編程之美）
? ? ?該文章原理說得比較清楚：[點擊打開鏈接](http://www.cnblogs.com/tianchi/archive/2013/02/25/2886964.html)
? ? ?這里是代碼：[點擊打開鏈接](http://blog.csdn.net/zzran/article/details/8274735)
5、求每一對頂點之間的最短路徑：Floyd-Warshall算法
- 前言
- Josephus約瑟夫問題及其變種
- 鏈表的常見實現
- 二叉樹遍歷、插入、刪除等常見操作
- 二叉堆的插入刪除等操作C++實現
- 插入排序和希爾排序
- 堆排序
- 歸并排序及其空間復雜度的思考
- 快速排序的幾種常見實現及其性能對比
- 紅黑樹操作及實現
- 整數的二進制表示中1的個數
- 位操作實現加減乘除四則運算
- 冒泡排序的改進
- 直接選擇排序
- 不借助變量交換兩個數
- 基礎排序算法總結
- AVL樹（Adelson-Velskii-Landis tree）
- avl樹的C++實現
- 動態規劃之鋼條分割
- hash函數的基本知識
- 動態規劃：求最長公共子串/最長公共子序列
- 最長遞增子序列
- 稱砝碼問題
- 汽水瓶
- 字符串合并處理（二進制位的倒序）
- 動態規劃：計算字符串相似度
- m個蘋果放入n個盤子
- 生成k個小于n的互不相同的隨機數
- 棧和隊列的相互模擬
- 字符串的排列/組合
- KMP(Knuth-Morris-Pratt)算法
- n個骰子的點數
- 位運算的常見操作和題目