[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;}