poj 3080 PKU 3080 Blue Jeans(kmp)
?
#include<stdio.h>
#include<string.h>
const int N=100;
int n,m,next[N];
char dna[N][N];
void get_next(char *str,int len)
{
next[0]=-1;
int j=0,k=-1;//k记录next[];
while(j<len)
{
if(k==-1||str[j]==str[k])
{
k++;
j++;
if(str[k]!=str[j])
next[j]=k;
else next[j]=next[k];
}
else k=next[k];
}
}
int kmp(char *s,int slen)
{
get_next(s,slen);
int f=0,j,k,i;
for(i=1;i<m;i++)
{
int k=0, j=0;
int len=strlen(dna[i]);
while(j<len&&k<slen)
{
if(k==-1||s[k]==dna[i][j])
{
j++;
k++;
}
else k=next[k];
}
if(k<slen)break;
}
if(i==m)return 1;
else return 0;
}
int main()
{
int i,j,k,sum,max=-1;
char s[63],ans[63];
scanf("%d",&n);
while(n--)
{
max=-1;
scanf("%d",&m);
getchar();
for(i=0;i<m;i++)
{
gets(dna[i]);
}
int len=strlen(dna[0]);
for(i=0;i<len;i++)
{
for(j=i;j<len;j++)
{
sum=0;
for(k=i;k<=j;k++)
{
s[sum++]=dna[0][k];
}
s[sum]='\0';
if(kmp(s,sum)==1)
{
if(sum>max)
{
strcpy(ans,s);
max=sum;
}
else
{
if(max==sum&&strcmp(ans,s)>0)
{
strcpy(ans,s);
}
}
}
}
}
if(max<3)printf("no significant commonalities\n");
else printf("%s\n",ans);
}
}
编辑器加载中...