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

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

题意:

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

分析:

       本题不用输出子序列,很简单,直接处理即可.

       首先令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;
}

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