先來講解以下什么是最長(zhǎng)公共子序列。最長(zhǎng)公共子序列不是最長(zhǎng)相同字符串，有點(diǎn)相似但不一樣，來舉個(gè)簡(jiǎn)單的例子，有字符串s1=bcdea，s2=abce，最長(zhǎng)相同字符串是bc，最大公共部分是2；而最長(zhǎng)公共子序列則是bce，最大公共部分是3?？梢钥闯?，公共子序列不需要連續(xù)相等，有相同的序列即可。
明白了概念之后，我們來看一下題目。
2-1 兩個(gè)字符串的所有最長(zhǎng)公共子序列 (轉(zhuǎn)自PTA)
求兩個(gè)字符串的所有最長(zhǎng)公共子序列。
輸入格式:
輸入長(zhǎng)度≤100的兩個(gè)字符串。
輸出格式:
輸出兩個(gè)字符串的所有最長(zhǎng)公共子序列，若最長(zhǎng)公共子序列多于1個(gè)，則將所有子序列按字典序從小到大排序后輸出。
輸入樣例1:
ABCBDAB
BDCABA
輸出樣例1:
BCAB
BCBA
BDAB
輸入樣例2:
ABACDEF
PGHIK
輸出樣例2:
NO讀完題目之后還有點(diǎn)懵的話，那就先聽一下我的思路。本題要輸出的是最長(zhǎng)公共子序列，可能的情況可以分為三種：不存在、只有一條和有多條。如果我們逐個(gè)去枚舉的話，如果遇到存在多條的情況，是很容易出錯(cuò)并且漏選。那我們可以先求出其最長(zhǎng)的長(zhǎng)度是多少，再用回溯法，一一找出。
求最大公共子序列的長(zhǎng)度
string s1, s2;
int arr[101][101]={0};//動(dòng)態(tài)規(guī)劃表
set <string> lsc_s;
int lsc_max(int m, int n)//求出最大公共子序列的長(zhǎng)度
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s1[i-1]==s2[j-1])arr[i][j]=arr[i-1][j-1]+1;
else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
}
}
return arr[m][n];
}s1、s2是要輸入的兩個(gè)字符串，set是集合（后面再講）。我們?cè)趺磥肀容^呢，設(shè)立一個(gè)二維表，即上面的arr，字符串s1為縱列，字符串s2為橫行。
首先拿出s1中的第一個(gè)字符和s2中逐一比較，可得出b行b列的意思是s1中b和s2中ab比較，有1個(gè)公共的，故為1；b行c列是s1中b和s2中abc比較，也只有一個(gè)公共，也為1；再舉一個(gè)例子，e行e列是s1中bcde和s2中abce比較，因?yàn)閑和e相同，并且前面s1中bcd和s2中abc比較時(shí)已經(jīng)有兩個(gè)公共的了，所以要2+1=3；以此類推，可得出此表，同時(shí)我們也可以得出一條遞推公式，即
if s1[i]==s2[j]，arr[i][j]=arr[i-1][j-1]+1；
else arr[i][j]=max{ arr[i][j-1], arr[i-1][j] };
即可得出最長(zhǎng)公共子序列的最大長(zhǎng)度arr[i][j]。下一步就可根據(jù)回溯法來獲取公共子序列的所有序列并打印。
打印所有最長(zhǎng)公共子序列
void lsc_print(int i, int j, string str)
{
while(i>0&&j>0)
{
if(s1[i-1]==s2[j-1])
{
i--;
j--;
str=s1[i]+str;
}
else
{
if(arr[i-1][j]>arr[i][j-1])i--;
else if(arr[i-1][j]<arr[i][j-1])j--;
else
{
lsc_print(i-1,j,str);
lsc_print(i,j-1,str);
return;
}
}
}
if(str.length())lsc_s.insert(str);
}從arr[i][j]開始回溯，當(dāng)s1[i-1]==s2[j-1]時(shí)，說明此公共子序列中包括這個(gè)元素，即可把這個(gè)元素加入到臨時(shí)變量str中（頭插法），因?yàn)槭腔厮?，滿足條件的元素在前面；當(dāng)s1[i-1]!=s2[j-1]時(shí)，說明arr[i][j]是由arr[i-1][j]或者arr[i][j-1]繼承而來，所以可以判斷這兩個(gè)哪個(gè)比較大，就跑去那邊，當(dāng)兩邊一樣大的時(shí)候，說明可能存在不同的最長(zhǎng)子序列，所以可以進(jìn)行遞歸分別求解。當(dāng)回溯完成后，把str放入到set容器中儲(chǔ)存起（為什么用set不用數(shù)組，因?yàn)轭}目要求按字典序從小到大輸出，set底層是紅黑樹，自動(dòng)幫我們排列好，感興趣的同學(xué)可以去看看set用法和底層操作）。
最終ac代碼如下：文章來源：http://www.zghlxwxcb.cn/news/detail-418204.html
#include<iostream>
#include<string>
#include<set>
using namespace std;
string s1, s2;
int arr[101][101]={0};//動(dòng)態(tài)規(guī)劃表
set <string> lsc_s;
int lsc_max(int m, int n)//求出最大公共子序列的長(zhǎng)度
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s1[i-1]==s2[j-1])arr[i][j]=arr[i-1][j-1]+1;
else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
}
}
return arr[m][n];
}
void lsc_print(int i, int j, string str)
{
while(i>0&&j>0)
{
if(s1[i-1]==s2[j-1])
{
i--;
j--;
str=s1[i]+str;
}
else
{
if(arr[i-1][j]>arr[i][j-1])i--;
else if(arr[i-1][j]<arr[i][j-1])j--;
else
{
lsc_print(i-1,j,str);
lsc_print(i,j-1,str);
return;
}
}
}
if(str.length())lsc_s.insert(str);
}
int main()
{
cin>>s1>>s2;
int m=s1.length();
int n=s2.length();
int len=lsc_max(m,n);
string str;
lsc_print(m, n, str);
set<string>::iterator it=lsc_s.begin();
if(lsc_s.empty())
{
cout<<"NO"<<endl;
return 0;
}
while(it!=lsc_s.end())
{
cout<<*it<<endl;
it++;
}
return 0;
}
如果本篇文章對(duì)你有所幫助的話，記得點(diǎn)贊哦！如果哪里寫得不好的話，也可以評(píng)論，歡迎指正！文章來源地址http://www.zghlxwxcb.cn/news/detail-418204.html
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——最長(zhǎng)公共子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
