lcs存路径p2264.cpp

动态规划的代码~LCS存路径DP：）状态压缩。。

/*
    poj 2264 比较经典的  LCS 存路径问题，
     sunmoonstar_love 极力推荐 
*/
#include <iostream>
#include <string>
using namespace std;
int f[2][71],i,j,n,la,lb,t;
string a,b,s[2][71],tmp;

int main()
{
    while(cin>>a>>b)
    {
        la = a.length();
        lb = b.length();
        for(i=0; i<71; i++)
        {
            s[0][i]=s[1][i]="";
            f[0][i]=f[1][i] = 0;
        }    
        for(i=1; i<=la; i++)
        {
            for(j=1; j<=lb; j++)
            {
                if(a[i-1]==b[j-1])
                {
                    f[i%2][j] = f[(i+1)%2][j-1]+1;
                    s[i%2][j] = s[(i+1)%2][j-1]+a[i-1];
                }
                else
                {
                    f[i%2][j] = f[(i+1)%2][j];
                    s[i%2][j] = s[(i+1)%2][j];
                    if(f[i%2][j]<f[i%2][j-1])
                    {
                        f[i%2][j] = f[i%2][j-1];
                        s[i%2][j] = s[i%2][j-1];
                    }    
                }        
            }    
        }
        tmp = s[la%2][lb];
        i = 0;j=0;t=0;
        while(i<la)
        {
            if(a[i]!=tmp[t])
            {
                cout<<a[i];
                i++;
            }
            else
            {
                while(j<lb&&b[j]!=tmp[t])
                {
                    cout<<b[j];
                    j++;
                }
                if(j==lb)
                    break;  
                cout<<tmp[t++];
                j++; i++;                  
            }        
        }
        if(i==la&&j!=lb)
        {
            while(j<lb)
                cout<<b[j++];
        }
        if(j==lb&&i!=la)
        {
            while(i<la)
                cout<<a[i++];
        }            
        cout<<endl;  
        a = b = "";      
    }    
    return 0;
}