#include <iostream> //KMP+枚舉
#include<string>
using namespace std;
#define len 60
char str[10][100],base[100];
int next[100];
void get_next(char B[],int t) //B[1]--B[t]
{
next[1]=0;
int j=0;
for(int i=2;i<=t;++i)
{
while(j>0&&B[j+1]!=B[i])
j=next[j];
if(B[j+1]==B[i])
j=j+1;
next[i]=j;
}
}
bool kmp(char A[],char B[],int t) //A是主串,B是子串,查詢B串在A串的哪些地方出現(xiàn)
{
int j=0;
for(int i=1;i<=len;++i)
{
while(j>0&&B[j+1]!=A[i])
j=next[j];
if(B[j+1]==A[i])
j=j+1;
if(j==t)
return true;
}
return false;
}
int main()
{
int cases,m;
char res[100],tmp[100];
cin>>cases;
while(cases--)
{
cin>>m;
for(int i=0;i<m;++i)
scanf("%s",str[i]+1); //下標從1開始
int tag=1,flag=1,rear=0;
strcpy(res,"");
for(int i=len;i>=3&&flag;--i)
{
for(int j=1;j+i-1<=len;++j)
{
for(int k=j;k<j+i;++k)
base[k-j+1]=str[0][k]; //base[1]--base[i]
get_next(base,i);
tag=0;
for(int k=1;k<m;++k)
if(!kmp(str[k],base,i))
{
tag=1;break;
}
if(tag==0)
{
flag=0;
strncpy(tmp,base+1,i); //把base[1..i]復(fù)制到tmp[0..i-1]
tmp[i]=0;
if(strlen(res)==0||strcmp(res,tmp)>0) //字典排序的最小串
strcpy(res,tmp);
}
}
}
if(flag==1)
printf("no significant commonalities\n");
else
printf("%s\n",res);
}
return 0;
}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/mjc467621163/archive/2011/07/22/2114496.html

總結(jié)

以上是生活随笔為你收集整理的poj 3080 Blue Jeans的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。