SPOJ TRIP

SPOJ_TRIP.cpp

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 85;
char s[2][SIZE];
int dp[SIZE][SIZE];
int n[2];
int nxt[2][SIZE][26];
char an[SIZE];
void dfs(int id1,int id2,int pos){
    if(dp[id1][id2]==0){
        puts(an);
        return;
    }
    for(int i=0;i<26;i++){
        an[pos]=i+'a';
        if(nxt[0][id1][i]<n[0] && nxt[1][id2][i] < n[1] && dp[id1][id2]==dp[nxt[0][id1][i]+1][nxt[1][id2][i]+1]+1)
            dfs(nxt[0][id1][i]+1,nxt[1][id2][i]+1,pos+1);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<2;i++){
            scanf("%s",s[i]);
            n[i]=strlen(s[i]);
            for(int j=0;j<26;j++)nxt[i][n[i]][j]=n[i];
            for(int j=n[i]-1;j>=0;j--){
                for(int k=0;k<26;k++)nxt[i][j][k]=nxt[i][j+1][k];
                nxt[i][j][s[i][j]-'a']=j;
            }
        }
        for(int i=n[0]-1;i>=0;i--)
            for(int j=n[1]-1;j>=0;j--){
                if(s[0][i]==s[1][j])dp[i][j]=dp[i+1][j+1]+1;
                else dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
            }
        an[dp[0][0]]=0;
        dfs(0,0,0);
        if(T)puts("");
    }
    return 0;
}