[KMP或许暴力]POJ 3080 Blue Jeans

[KMP或者暴力]POJ 3080 Blue Jeans

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

题目大意：给定M个字符串（2<=M<=10），长度不超过60个字符，要求求出他们的最长公共子串，如果存在多个解，输出字典序最小的，如果该子串长度小于3，输出no ....(见题目描述)

思路：枚举某一个字符串的所有子串，拿去和剩余的所有字符串匹配，保存长度最大且字典序最小的即可，无所谓用KMP，暴力就行了，算法的主要时间花在枚举子串上面，这里为了练习KMP还是写了个KMP的匹配.

代码：

#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int MAXN = 11,MAXM = 66;char s[MAXN][MAXM],res[MAXM],temp[MAXM];int Next[MAXM];void MakeNext(char *str){ int M = strlen(str); int i = 0, j = -1;Next[0] = -1; while(i<M){ if(j==-1||str[i]==str[j])Next[++i]=++j; else j = Next[j]; }}int KMP(char *T,char *P){ int N = strlen(T), M = strlen(P); int i = 0, j = 0; while(i<N&&j<M){ if(j==-1||T[i]==P[j])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; else{ return strcmp(s1,s2)<0; }}int main(){ int n,m; scanf("%d",&n); while(n--){ scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%s",s[i]); } MakeNext(s[0]);res[0] = 0; int L = strlen(s[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; int ok = 1; for(int i=1;i<m;i++){ if(KMP(s[i],temp)==-1){ ok = 0; break; } } if(ok){ if(great(temp,res)){ strcpy(res,temp); } } } } int lr = strlen(res); if(lr<3){ printf("no significant commonalities\n"); }else{ printf("%s\n",res); } } return 0;}