【POJ 2250】Compromise(最长公共子序列LCS)

#include<cstdio>
#include<cstring>
#define N 102
#define M 32
int n,m,dp[N][N],ans[N][N];
char s1[N][M],s2[N][M],str[N][M];
void solve(){
    memset(dp,0,sizeof dp);
    memset(ans,0,sizeof ans);
    int i,j,t,ti;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (strcmp(s1[i-1],s2[j-1])==0)
                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];
                ans[i][j]=1;//从s1转移来
            }else
                dp[i][j]=dp[i][j-1];
    i=n,j=m;
    t=dp[n][m];
    while(i&&j)
        if(strcmp(s1[i-1],s2[j-1])==0){
            memcpy(str[--t],s1[i-1],sizeof s1[i-1]);
            i--;j--;
        }
        else{
            ti=i;
            i-=ans[i][j];
            j-=1^ans[ti][j];//ans=0则是s2转移来的，故j--
        }
    for(i=0;i<dp[n][m];i++) printf("%s ",str[i]);
    printf("\n");
}
int main(){
    while (~scanf("%s",&s1[n]))
        if (s1[n][0]=='#'){
            while (scanf("%s",&s2[m])&&s2[m][0]!='#') m++;
            solve();
            n=m=0;
        }
        else n++;
    return 0;
}