poj 3080 Blue Jeans

本文主要是介绍poj 3080 Blue Jeans，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求n个字符串的大于三的最长公共子序列。
kmp+暴搜枚举即可。
#include<stdio.h>
#include<string.h>
char str[10][65];
char ans[65],s[65];
int next[65];
int t,n,max,num;
void get_next(char *s,int slen)
{
int i=-1,j=0;
memset(next,0,sizeof(next));
next[0]=-1;
while(j<slen)
{
if(i==-1||s[i]==s[j]) 
{
i++;
j++;
next[j]=i;
}
else i=next[i];
}
}
int kmp(char *s,int slen)
{
get_next(s,slen);
int i;
for(i=1;i<n;i++)
{
int len=strlen(str[i]);
int j=0,k=0;
while(j<len&&k<slen)
{
if(s[k]==str[i][j])
{
k++;
j++;
}
else
{
k=next[k];
if(k==-1)
{
k=0;
j=j+1;
}
}
}
if(k<slen)break;
}
if(i==n)  return 1;
else  return 0;
}      
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
max=2;
for(int i=0;i<n;i++)
scanf("%s",str[i]);
int len=strlen(str[0]);
for(int i=0;i<len;i++)
for(int j=i+2;j<len;j++)
{
num=0;
for(int k=i;k<=j;k++)
{
s[num++]=str[0][k];
s[num]=0;
if(kmp(s,num))
{
if(num>max)
{
max=num;
strcpy(ans,s);
}  
else if(num==max&&strcmp(ans,s)>0)
{
strcpy(ans,s);
}
}
}
}
if(max>=3)  printf("%s\n",ans);
else printf("no significant commonalities\n");
}
return 0;
}

这篇关于poj 3080 Blue Jeans的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---