基礎(chǔ)概念
- 字符串：S[0..n]婆咸，S是一個(gè)字符串谈截，長(zhǎng)度為n筷屡。S本質(zhì)上是一個(gè)字符數(shù)組，數(shù)組的每個(gè)元素都是一個(gè)字符簸喂；
- 子序列：設(shè)T為S的一個(gè)子序列毙死，則如果T[ti]和T[tj]為T(mén)的兩個(gè)字符，ti<tj喻鳄，那么T[ti]和T[tj]也都是S的字符扼倘，且對(duì)應(yīng)的下標(biāo)si<sj。舉個(gè)例子除呵，S為adbfhgs再菊，那么abfg就是S的一個(gè)子序列爪喘，abcfg就不是S的子序列；
- 子串：子串是一種特殊的子序列袄简，它要求tj - ti = sj - si腥放，即子串的字符要在S中連續(xù)。還是設(shè)S為adbfhgs绿语，那么adbf是S的一個(gè)子串秃症，abfg就不是。
- 后綴：S[0..n]吕粹，那么S[i..n] (i>=0)都是S的后綴种柑；
- 公共子序列/串：如果R既是S的子序列/串，又是T 的子序列/串匹耕，那么R就是S和T 的公共子序列/串聚请。
最長(zhǎng)公共子序列
問(wèn)題描述
有兩個(gè)字符串S[0...m]和T[0...n]，求S和T的所有最長(zhǎng)公共子序列的長(zhǎng)度稳其。
例子
設(shè)S=adbfhgs驶赏，T=hadeubgs，那么S和T的最長(zhǎng)公共子序列為R=adbgs既鞠，長(zhǎng)度為5煤傍。
分析
首先考慮暴力求解。枚舉S的所有子序列嘱蛋，總共有2m個(gè)蚯姆；然后再枚舉T的所有子序列，總共有2n個(gè)洒敏；最后一一匹配龄恋，總的時(shí)間復(fù)雜度為O(2^(m+n))。顯然是不可行的凶伙。
考慮一種動(dòng)態(tài)規(guī)劃的方法郭毕。
-
狀態(tài)表####
dp[i][j]，i和j分別是S和T的下標(biāo)函荣，dp[i][j]為當(dāng)前狀態(tài)下的最長(zhǎng)公共子序列的長(zhǎng)度铣卡。其中i和j分別從0開(kāi)始遞增，即狀態(tài)表是從左往右偏竟，從上往下依次被填滿的（假設(shè)左上方的i和j都是0）煮落。
-
基礎(chǔ)狀態(tài)####
dp[0][j]=0，dp[i][0]=0踊谋。顯然當(dāng)一個(gè)字符串為空時(shí)蝉仇，兩字符串的最長(zhǎng)公共子序列就是空字符串，長(zhǎng)度為0
-
狀態(tài)轉(zhuǎn)移方程####
dp[i][j]=dp[i-1][j-1]+1, S[i]=T[j];
dp[i][j]=max(dp[i-1][j],dp[i][j-1]), S[i]!=T[j].
當(dāng)S[i]=T[j]時(shí)，如果i-1和j-1狀態(tài)下的最長(zhǎng)公共子序列為R轿衔，那么i和j狀態(tài)下的最長(zhǎng)公共子序列就為R+S[i] (T[j])沉迹，所以長(zhǎng)度會(huì)加1；
當(dāng)S[i]!=T[j]害驹，i和j狀態(tài)下的最長(zhǎng)公共子序列要么是i-1和j狀態(tài)下的最長(zhǎng)公共子序列鞭呕，要么是i和j-1狀態(tài)下的最長(zhǎng)公共子序列，所以長(zhǎng)度取這兩個(gè)最長(zhǎng)公共子序列的長(zhǎng)度的最大值宛官。
打印
到目前為止葫松，我們已經(jīng)得到了一張?zhí)詈玫臓顟B(tài)表。那么怎么通過(guò)這張狀態(tài)表打印出對(duì)應(yīng)的最長(zhǎng)公共子序列呢底洗？
從狀態(tài)表的右下方開(kāi)始腋么，向上回溯。具體算法詳見(jiàn)代碼亥揖。
代碼
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int slen = s.length();
int tlen = t.length();
vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));
for (int i = 1; i <= slen; i++)
for (int j = 1; j <= tlen; j++)
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
int lcslen = dp[slen][tlen]; // 最長(zhǎng)公共子序列長(zhǎng)度
string lcs; // 最長(zhǎng)公共子序列
lcs.resize(lcslen);
// 從右下向左上遍歷狀態(tài)表
int i = slen, j = tlen, k = lcslen;
while (i > 0 && j > 0)
{
if (s[i - 1] == t[j - 1])
{
lcs[--k] = s[i - 1];
i--; j--;
}
else if (dp[i - 1][j] < dp[i][j - 1])
j--;
else
i--;
}
cout << "longest common subsequence length: " << lcslen << endl;
cout << "longest common subsequence: " << lcs << endl;
return 0;
}
最長(zhǎng)公共子串
問(wèn)題描述
有兩個(gè)字符串S[0...m]和T[0...n]珊擂，求S和T的所有最長(zhǎng)公共子串的長(zhǎng)度。
例子
設(shè)S=adbfhgs费变，T=hadeubgs摧扇，那么S和T的最長(zhǎng)公共子串為R=ad或者gs，長(zhǎng)度為2挚歧。
分析
首先考慮暴力求解扳剿。枚舉S的所有子串，總共有(m2+m)/2個(gè)昼激；然后再枚舉T的所有子序列，總共有(n2+n)/2個(gè)锡搜；最后一一匹配橙困，總的時(shí)間復(fù)雜度為O(m2*n2)，也是不可行的耕餐》哺担可以使用KMP算法把匹配的復(fù)雜度降到O(n)，但是總的復(fù)雜度O(m^2*n)還是太高肠缔。
考慮一種動(dòng)態(tài)規(guī)劃的方法夏跷。
-
狀態(tài)表####
dp[i][j]，i和j分別是S和T的下標(biāo)明未。注意槽华，這里的dp[i][j]并不是當(dāng)前狀態(tài)下的最長(zhǎng)公共子串的長(zhǎng)度，而是最長(zhǎng)公共后綴的長(zhǎng)度趟妥。舉個(gè)例子猫态，S為abxcdef，T為frcdef，當(dāng)i=4亲雪，j=3勇凭，即i指向d，j指向也是d义辕，則當(dāng)前字符串a(chǎn)bxcd和frcd的最長(zhǎng)公共后綴為cd虾标。要明確后綴就是從后往前看，依次進(jìn)行匹配就行了灌砖。其中i和j分別從0開(kāi)始遞增璧函，即狀態(tài)表是從左往右，從上往下依次被填滿的（假設(shè)左上方的i和j都是0）周崭。
-
基礎(chǔ)狀態(tài)####
dp[0][j]=0柳譬，dp[i][0]=0。顯然當(dāng)一個(gè)字符串為空時(shí)续镇，兩字符串的最長(zhǎng)公共子串就是空字符串美澳，長(zhǎng)度為0
-
狀態(tài)轉(zhuǎn)移方程####
dp[i][j]=dp[i-1][j-1]+1, S[i]=T[j];
dp[i][j]=0, S[i]!=T[j];
lcslen=max(lcslen, dp[i][j]).
當(dāng)S[i]=T[j]時(shí)，如果i-1和j-1狀態(tài)下的最長(zhǎng)公共后綴為R摸航，那么i和j狀態(tài)下的最長(zhǎng)公共后綴就為R+S[i] (T[j])制跟，所以長(zhǎng)度會(huì)加1；設(shè)S為abxcdef酱虎，T為frcdef雨膨，i=4(指向d)，j=3(指向d)读串，i-1和j-1狀態(tài)下的最長(zhǎng)公共后綴為c聊记，i和j狀態(tài)下的最長(zhǎng)公共后綴就是cd，長(zhǎng)度為2恢暖；
當(dāng)S[i]!=T[j]排监，設(shè)S為abxcdef，T為frcdef杰捂，i=4(指向d)舆床，j=4(指向e)，則當(dāng)前字符串a(chǎn)bxcd和frcde的最長(zhǎng)公共后綴為空嫁佳，長(zhǎng)度為0挨队。
lcslen是最長(zhǎng)公共子串的長(zhǎng)度，每次更新?tīng)顟B(tài)的時(shí)候更新蒿往。
打印
構(gòu)建狀態(tài)表的時(shí)候盛垦，保存每次檢測(cè)到的最長(zhǎng)公共子串的尾下標(biāo)，最后從尾下標(biāo)開(kāi)始往前查找字符串瓤漏，直到找到兩個(gè)不相同的字符為止情臭。
代碼
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int slen = s.length();
int tlen = t.length();
vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));
int lcsi, lcsj; // 最長(zhǎng)公共子串的尾下標(biāo)
int lcslen = 0; // 最長(zhǎng)公共子串長(zhǎng)度
for (int i = 1; i <= slen; i++)
for (int j = 1; j <= tlen; j++)
if (s[i - 1] == t[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > lcslen)
{
lcslen = dp[i][j];
lcsi = i;
lcsj = j;
}
}
string lcs;// 最長(zhǎng)公共子串
lcs.resize(lcslen);
for (int i = lcsi - 1, j = lcsj - 1, k = lcslen;
i >= 0 && j >= 0; )
{
if (s[i] == t[j])
{
lcs[--k] = s[i];
i--; j--;
}
else
break;
}
cout << "longest common substring length: " << lcslen << endl;
cout << "longest common substring: " << lcs << endl;
return 0;
}
