[KMP或者暴力]POJ 3450 Corporate Identity

传送门：http://poj.org/problem?id=3450

题目大意：前面那道题类似，求多个字符串的最长且字典序最小的公共子串，还是枚举子串，然后拿去和剩余主串匹配，保存最优解。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 222,MAXM = 4444;
char s[MAXM][MAXN],temp[MAXN],res[MAXN];
int next[MAXN],n;
void makenext(char *str){
    int i = 0,j = -1,M = strlen(str);
    next[0] = -1;
    while(i<M){
        if(str[i]==str[j]||j==-1)next[++i] = ++j;
        else j = next[j];
    }
}
int KMP(char *T,char *P){
    int N = strlen(T),M = strlen(P),i = 0,j = 0;
    while(i<N&&j<M){
        if(T[i]==P[j]||j==-1)i++,j++;
        else j = next[j];
    }
    return j==M?i-M:-1;
}
bool great(char *s1,char *s2){
    int l1 = strlen(s1),l2 = strlen(s2);
    if(l1!=l2)return l1>l2;
    return strcmp(s1,s2)<0;
}
int main(){
    while(scanf("%d",&n),n){
        for(int i=0;i<n;i++)scanf("%s",s[i]);
        int l = strlen(s[0]);res[0] = 0;
        for(int i=0;i<l;i++){
            for(int j=i;j<l;j++){
                for(int k=0;k<j-i+1;k++){
                    temp[k] = s[0][k+i];
                }
                temp[j-i+1] = 0;
                makenext(temp);
                int ok = 1;
                for(int k=1;k<n;k++){
                    if(KMP(s[k],temp)==-1){
                        ok = 0;break;
                    }
                }
                //cout<<temp<<" "<<ok<<endl;
                if(ok&&great(temp,res)){
                    strcpy(res,temp);
                }
            }
        }
        if(res[0]){
            printf("%s\n",res);
        }else{
            printf("IDENTITY LOST\n");
        }
    }
    return 0;
}