话说这道题我调试了5个小时,整整一晚上啊!!!!!!!!!!!!!!
说一下思路就是枚举第一个字符串所有的子串长度,去与其余的字符串kmp,如果都符合,那那个子串的长度就是答案!!!
#include<iostream> using namespace std; #define max 105 int next[max]; void prekmp(char aa[]) { int j=-1; next[0]=-1; int len=strlen(aa); for(int i=1;i<len;i++) { if(j>=0&&aa[i]!=aa[j+1]) j=next[j]; if(aa[i]==aa[j+1]) j++; next[i]=j; } } int kmp(char ss[],char a[]) { // cout<<ss<<' '<<a; // system("pause"); prekmp(ss); int len=strlen(a); int lens=strlen(ss); // for(int i=0;i<lens;i++) // cout<<next[i]<<' '; // system("pause"); int j=-1; // cout<<len; // system("pause"); for(int i=0;i<len;i++) { // cout<<j<<' '<<lens<<' '<<a<<' '<<ss; // system("pause"); if(j>=0&&ss[j+1]!=a[i]) j=next[j]; if(ss[j+1]==a[i]) j++; // next[i]=j;//最关键的是我多加了这步,这里的next就是在子串ss数组里来回指,看j能不能知道子串ss数组末尾,而这步把j在next里指向a数组的范围了,所以加这部指定错!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! // if(j==0) // j=-1; // cout<<j<<' '<<len; // system("pause"); if(j==lens-1) return 1; } return 0; } int main() { char a[max][max]; char ta[max],tb[max]; int t,n; cin>>t; while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s",a[i]); int len=strlen(a[1]); int sign=0,sign1=0; int i; for( i=len;i>=1;i--) { for(int j=0;j+i-1<len;j++) { int cou=0; for(int k=j;k<=j+i-1;k++) ta[cou++]=a[1][k]; ta[cou]='\0'; // for(int i=0;i<cou;i++) // cout<<ta[i]<<' '; // system("pause"); cou=0; for(int k=j+i-1;k>=j;k--) tb[cou++]=a[1][k]; tb[cou]='\0'; // cout<<ta; // system("pause"); cou=0; for(int k=2;k<=n;k++) { // system("pause"); if(kmp(ta,a[k])||kmp(tb,a[k])) { cou++; } } if(cou==n-2+1) { // cout<<ta; // system("pause"); sign=1; sign1=1; printf("%d\n",i); break; } } if(sign==1) break; } if(sign1==0) printf("0\n"); } // system("pause"); return 0; }