最长公共子序列-蒲公英云

最长公共子序列

港控/mmm° 2022-04-23 07:04 404阅读 0赞

最长公共子序列问题，具有最优子结构性质

      **设序列****X****m****=\{x****1****,x****2****,…,****x****m****\}****和****Y****n****=\{y****1****,y****2****,…,****y****n****\}****的最长公共子序列为****Z****k****=\{z****1****, z****2****,…,** **z****k****\}** **，则**

l 若**xm=yn 则 zk=xm=y**n 且 Z**k-1是Xm-1和 Yn-1的最长公共子序列。**

l 若**xm≠y**n 且 z**k≠xm 则 Z是Xm-1和 Y 的最长公共子序列**

l 若**xm≠y**n 且 z**k≠yn 则 Z是Xm和 Y**n-1 的最长公共子序列

由此可见，**2个序列的最长公共子序列包含了这2**个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70

对应的代码如下：

#include<bits/stdc++.h>
using namespace std;
//最长公共子序列 
int main(){
    string a,b;
    cin>>a>>b;
    int c[100][100],n1=a.length(),n2=b.length();
    for(int i=1;i<=n1;i++)c[i][0]=0;//也就是说：a串中第i个字符和b串中第0个字符的公共子序列为长度为0；
    for(int i=1;i<=n2;i++)c[0][i]=0;//也就是说：b串中第i个字符和a串中第0个字符的公共子序列为长度为0；(注意抽象化)
    for(int i=1;i<=n1;i++)
        for(int j=1;j<=n2;j++)
            if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;
            else c[i][j]=max(c[i-1][j],c[i][j-1]);    
    cout<<c[n1][n2];
    return 0;
}

关于最长公共子序列的另外一类问题是输出它的最长公共子序列，这样只需要在每次更新c [ i ] [ j ]的时候，记录一下更新的种类

代码如下

void LCS**(**int i**，**int j**，char *x，**int **b)

{

if (**i ==0 || j==0) return;**

if (b[**i**][j]== 1)

{ LCS**(i-1，j-1，x，b);**

                             **printf****(“%c ”, x\[****i****\]);                         \}**

else

if (b[**i**][j]== 2)

                            **LCS****(i-1****，****j****，****x****，****b);**

else

                         **LCS****(****i****，****j-1****，****x****，****b);**

}

完整代码：

#include<bits/stdc++.h>
using namespace std;
void  output(int i,int j,string a,string b){
    if(!i||!j)return 0;
    if(b[i][j]=1){
        output(i-1,j-1,a,b);
        cout<<a[i-1];
    }else if(b[i][j]==2){
        output(i-1,j,a,b);    
    }else{
        output(i,j-1,a,b);
    }
}
int main(){
    string a,b;
    cin>>a>>b;
    int b[100][100],c[100][100],n1=a.length(),n2=b.length();
    for(int i=1;i<=n1;i++)c[i][0]=0;
    for(int i=1;i<=n2;i++)c[0][i]=0;
    for(int i=1;i<=n1;i++)
        for(int j=1;j<=n2;j++)
            if(a[i-1]==b[j-1]){
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]=1;
            }else{
                if(c[i-1][j]>=c[i][j-1]){
                    c[i][j]=c[i-1][j];
                    b[i][j]=2;
                }else{
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
}