LCS + Problem
longest comment subsequence
最长公共子序列（LCM）
最长公共子序列，。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
（1）字符子串：指的是字符串中连续的n个字符，如abcdefg中，ab，cde，fg等都属于它的字串。
（2）字符子序列：指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如abcdefg中，acdg，bdf属于它的子序列，而bac，dbfg则不是，因为它们与字符串的字符顺序不一致。
(3) 公共子序列：如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。如对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说，序列1,8,7是它们的一个公共子序列。
那么现在，我们再通俗的总结一下最长公共子序列（LCS）：就是A和B的公共子序列中长度最长的（包含元素最多的）
我们用Ax表示序列A的连续前x项构成的子序列，即Ax= a1,a2,……ax, By= b1,b2,……by, 我们用LCS(x, y)表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用L(x, y)表示Ax和By的一个最长公共子序列。让我们来看看如何求LCS(x, y)。我们令x表示子序列考虑最后一项
（1） Ax ＝ By
那么它们L(Ax, By)的最后一项一定是这个元素！
为什么呢？为了方便，我们令t = Ax = By, 我们用反证法：假设L(x,y)最后一项不是t，则要么L(x,y)为空序列（别忘了这个），要么L(x,y)的最后一项是Aa＝Bb ≠ t, 且显然有a < x, b < y。无论是哪种情况我们都可以把t接到这个L(x,y)后面,从而得到一个更长的公共子序列。矛盾！ 如果我们从序列Ax中删掉最后一项ax得到Ax-1,从序列By中也删掉最后一项by得到By-1，(多说一句角标为0时，认为子序列是空序列)，则我们从L(x,y)也删掉最后一项t得到的序列是L(x – 1, y - 1)。为什么呢？和上面的道理相同，如果得到的序列不是L(x - 1, y - 1)，则它一定比L(x - 1, y - 1)短（注意L（，）是个集合！），那么它后面接上元素t得到的子序列L(x,y)也比L(x - 1, y - 1)接上元素t得到的子序列短，这与L(x, y)是最长公共子序列矛盾。因此L(x, y) = L(x - 1, y - 1) 最后接上元素t，LCS(Ax, By) = LCS(x - 1, y - 1) + 1。
（2） Ax ≠ By
仍然设t = L(Ax, By), 或者L(Ax, By)是空序列（这时t是未定义值不等于任何值）。则t ≠ Ax和t ≠ By至少有一个成立，因为t不能同时等于两个不同的值嘛！
（2.1）如果t ≠ Ax，则有L(x, y)= L(x - 1, y)，因为根本没Ax的事嘛。
LCS(x,y) = LCS(x – 1, y)
（2.2）如果t ≠ By,l类似L(x, y)= L(x , y - 1)
LCS(x,y) = LCS(x, y – 1)
可是，我们事先并不知道t，由定义，我们取最大的一个，因此这种情况下,有LCS(x,y) = max(LCS(x – 1, y) , LCS(x, y – 1))。看看目前我们已经得到了什么结论：
LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 （Ax ＝ By）
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) （Ax ≠ By）这时一个显然的递推式，光有递推可不行，初值是什么呢？显然，一个空序列和任何序列的最长公共子序列都是空序列！所以我们有:
LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
(3) 0 如果x = 0或者y = 0练习
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<string>
using namespace std;
int m,n;
char a[1010];
char b[1010];
int dp[1010][1010];
int main()
{
cin>>n>>m;
scanf("%s",a+1);
scanf("%s",b+1);
for(int i =1;i<=n;++i)
{
for(int j=1 ;j<=m;++j)
{
if(a[i]==b[j])
dp[i][j] = dp[i-1][j-1] + 1;
else if(dp[i-1][j]>dp[i][j-1])
dp[i][j] = dp[i-1][j];
else
{
dp[i][j] = dp[i][j-1];
}
}
}
cout<<dp[n][m]<<endl;
system("pause");
return 0;
}HDU1159
板子题
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
char a[1010],b[1010];
int dp[1001][1001];
int main()
{
while(~scanf("%s",a))
{
scanf("%s",b);
memset(dp,0,sizeof(dp));
int len1 = strlen(a);
int len2 = strlen(b);
for(int i =0;i<len1;++i)
{
for(int j =0;j<len2;++j)
{
if(a[i]==b[j])
dp[i+1][j+1] = dp[i][j] + 1;
// else if(dp[i][j+1]>dp[i+1][j])
// dp[i+1][j+1] = dp[i][j+1];
else
{
dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
//dp[i+1][j+1] = dp[i+1][j];
}
}
}
cout<<dp[len1][len2]<<endl;
//cout<<len1<<endl;
//cout<<len2<<endl;
}
return 0;
}51Nod1006
求的是最长公共子串是什么。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
char a[1010],b[1010];
int dp[1010][1010];
int main()
{
while(~scanf("%s",a+1))
{
scanf("%s",b+1);
int len1 = strlen(a+1);
int len2 = strlen(b+1);
string s;
for(int i =1;i<=len1;++i)
{
for(int j =1;j<=len2;++j)
{
if(a[i]==b[j])
dp[i][j] = dp[i-1][j-1] +1;
else
{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
int i = len1,j= len2;
while(i>=1&&j>=1)
{
if(a[i] == b[j])
{
s+=a[i];
i--;j--;
}
else if(dp[i-1][j]>dp[i][j-1])
i--;
else
{
j--;
}
}
reverse(s.begin(),s.end());
cout<<s<<endl;
s.clear();
// cout<<len1<<endl;
}
return 0;
}HDU1503
将两个字符串结合起来，他们的公共子串只输出一次
在LCS的基础之上加上路径记录，生成dp数组的时候做上标记，之后按顺序输出结果字符串。注意还要考虑一下没有公共子序列的情况。
#include<iostream>
#include<algorithm>
#include<cstring >
#include<string>
using namespace std;
int dp[110][110];
char a[110],b[110];
int main()
{
while(~scanf("%s",a+1))
{
scanf("%s",b+1);
int len1 = strlen(a+1);
int len2 = strlen(b+1);
memset(dp,0,sizeof(dp));
for(int i =1;i<=len1;++i)
{
for(int j=1;j<=len2;++j)
{
if(a[i]==b[j])
{
dp[i][j] = dp[i-1][j-1] +1;
}
else if(dp[i-1][j]>dp[i][j-1])
{
dp[i][j] = dp[i-1][j];
}
else
{
dp[i][j] = dp[i][j-1];
}
}
}
//cout<<dp[len1][len2]<<endl;
string s;
int i =len1,j=len2;
while(i>=1&&j>=1)
{
if(a[i] == b[j])
{
s+=a[i];
i--,j--;
}
else if(dp[i-1][j]>dp[i][j-1])
{
s+=a[i];
i--;
}
else
{
s+=b[j];
j--;
}
}
while(i!=0)
{
s+=a[i];
i--;
}
while(j!=0)
{
s+=b[j];
j--;
}
reverse(s.begin(),s.end());
cout<<s<<endl;
}
system("pause");
return 0;
}腾讯云开发者
