POJ1458 Common Subsequence(最长公共子序列LCS)

http://poj.org/problem?id=1458

题意:

给你两个字符串, 要你求出两个字符串的最长公共子序列长度.

分析:

本题不用输出子序列,非常easy,直接处理就可以.

首先令dp[i][j]==x表示A串的前i个字符和B串的前j个字符的最长公共子序列长度为x.

初始化: dp全为0.

状态转移:

IfA[i]==B[j] then

dp[i][j]= dp[i-1][j-1]+1

else

dp[i][j]= max( dp[i-1][j] , dp[i][j-1] )

上述公式: 当A[i]==B[j]时, A的第i个字符和B的第j个字符必定在A[1..i]和B[1..j]的最长公共子序列中, 所以dp[i][j]==dp[i-1][j-1]+1.

当A[i]!=B[j]时, A[i]和B[j]至少有一个是不可能在A[1..i]和B[1..j]的最长公共子序列中的, 所以dp[i][j] = max( dp[i-1][j] , dp[i][j-1] )

终于所求: dp[n][m].

AC代码:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=1000+5;

int n,m;

int dp[maxn][maxn];

char s1[maxn],s2[maxn];

int main()

{

    while(scanf("%s%s",s1,s2)==2)

    {

        n=strlen(s1);//s1串长度

        m=strlen(s2);//s2串长度

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            if(s1[i-1]==s2[j-1])

                dp[i][j]=dp[i-1][j-1]+1;

            else

                dp[i][j]=max( dp[i-1][j] , dp[i][j-1] );

        }

        printf("%d\n",dp[n][m]);

    }

    return 0;

}

如今的问题是怎样按字典序输出全部的LCS串呢?

能够看到假设我们想求A[1..i]与B[1..j]的LCS, 那么当A[i]==B[j]时,

A[i](也是B[j]字符)这个字符是必定要被选的, 那么我们以下考虑A[1..i-1]和B[1..j-1]的LCS就可以. 我写了一个DFS逆序递推求出全部串的方法, 然后把串保存入set中, 就是按字典序排序且去重后的结果了.

DFS过程事实上就是一个逆序递推的过程. S字符数组保存了我们当前已经确定了LCS的末尾num个字符. 假设当前A[i]==B[j], 那么A[i]就是一个我们须要保存入S的字符数组. 假设A[i]!=B[j], 那么我们最多有两条不同的路继续前进. 每一个DFS都是一条可行路, 必定会找到一个可行的LCS.

只是上面方法会出现非常多反复的串, 所以效率比較低. 假设想提高效率还须要记录每一个字符出现的位置并做一定的优化.

代码例如以下:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

#include<set>

using namespace std;

const int maxn=100+5;

int n,m;

int dp[maxn][maxn];

char s1[maxn],s2[maxn];

set<string> st;

char s[maxn];

char stmp[maxn];

int cnt;

//dfs从s1串的i位置和s2串的j位置開始逆序递推

//num是当前已经确定了LCS的末尾num个字符

//全部LCS保存到st中排序去重最后输出.

void dfs(int i,int j,int num)

{

    if(num>=cnt)//已经找到了一个LCS

    {

        for(int i=num;i>=1;i--)

            stmp[num-i]=s[i];

        stmp[num]='\0';

        string tmp(stmp);

        st.insert(tmp);

        return ;

    }

    if(s1[i]==s2[j])//该字符必选

    {

        s[++num]=s1[i];

        dfs(i-1,j-1,num);

    }

    else            //分情况讨论

    {

        if(dp[i-1][j]>dp[i][j-1])

            dfs(i-1,j,num);

        else if(dp[i-1][j]<dp[i][j-1])

            dfs(i,j-1,num);

        else

        {

            dfs(i-1,j,num);

            dfs(i,j-1,num);

        }

    }

}

int main()

{

    while(scanf("%s%s",s1,s2)==2)

    {

        n=strlen(s1);//s1串长度

        m=strlen(s2);//s2串长度

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            if(s1[i-1]==s2[j-1])

                dp[i][j]=dp[i-1][j-1]+1;

            else

                dp[i][j]=max( dp[i-1][j] , dp[i][j-1] );

        }

        printf("%d\n",dp[n][m]);

        cnt=dp[n][m];//cnt为LCS的长度

        dfs(n-1,m-1,0);

        set<string>::iterator it;

        for(it=st.begin(); it!=st.end(); ++it)

            cout<<*it<<endl;

    }

    return 0;

}