程式碼備份區

題意：

有兩個字串集(都吃到"#"為止)，問他們的最長相同子字串

解法：

LCS

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX(x,y)(((x)>(y))?(x):(y))
char strA[200][50];
char strB[200][50];
char ans[200][50];
int n=0;
int m=0;
int a=0;
int dp[200][200];
int LCS(int i,int j){
    if(dp[i][j]==-1){
        if(i<0 || j<0){
            dp[i][j] = 0;
        }else if(!strcmp(strA[i],strB[j])){
            dp[i][j] = LCS(i-1,j-1)+1;
        }else {
            dp[i][j] = MAX(LCS(i-1,j),LCS(i,j-1));
        }
    }
    return dp[i][j];
}
void load(int i,int j){
    if(i<0 || j<0)return;
    if(!strcmp(strA[i],strB[j])){
        load(i-1,j-1);
        strcpy(ans[a++],strA[i]);
    }else {
        if(dp[i][j]==dp[i-1][j]) load(i-1,j);
        else load(i,j-1);
    }
}
int main(){
    int i;
    while(scanf("%s",strA[n++])!=EOF){
        if(strA[0][0]!='#'){
            while(scanf("%s",strA[n])!=EOF && strA[n][0]!='#')++n;
        }
        while(scanf("%s",strB[m])!=EOF && strB[m][0]!='#')++m;
        memset(dp,-1,sizeof(dp));
        LCS(n-1,m-1);
        load(n-1,m-1);
        for(i=0;i<a;++i)printf("%s%c",ans[i],(i+1==a)?'\n':' ');
        n=m=a=0;
    }

    return 0;
}