社区首页 >专栏 >LCS + Problem

LCS + Problem

AngelNH

发布于 2020-04-16 07:41:05

54000

代码可运行

文章被收录于专栏：AngelNIAngelNI

运行总次数：0

代码可运行

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;
}