【poj 3080】Blue Jeans(字符串--KMP+暴力枚举+剪枝)

题意:求n个串的字典序最小的最长公共子串。

解法:枚举第一个串的子串,与剩下的n-1个串KMP匹配,判断是否有这样的公共子串。从大长度开始枚举,找到了就break挺快的。而且KMP的作用就是匹配子串,近乎O(n)的速度,很快。

P.S.对于字符串要仔细!!!

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int L=;
int n;
int next[],nextt[];
char s[][],ss[],str[]; bool kmp(int x,int l,int r)
{
/*for (int i=1;i<=L;i++)
{
if (!next[i]) nextt[i]=l-1;
else nextt[i]=next[i];
}WA!!*/
for (int i=l;i<=r;i++) ss[i-l+]=s[][i];
memset(next,,sizeof(next));
int p=;
next[]=;
for (int i=;i<=r-l+;i++)
{
while (ss[i]!=ss[p+] && p) p=next[p];
if (ss[i]==ss[p+]) p++;
next[i]=p;
}
p=;
for (int i=;i<=L;i++)
{
while (s[x][i]!=ss[p+] && p) p=next[p];
if (s[x][i]==ss[p+]) p++;
if (p==r-l+) return true;
}
return false;
}
bool check(int l,int r)
{
for (int i=;i<=n;i++)
if (!kmp(i,l,r)) return false;//O(n*n)匹配
return true;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%s",s[i]+);
bool ok=false;
for (int len=L;len>=;len--)
{
for (int i=;i+len-<=L;i++)
{
if (!check(i,i+len-)) continue;
memset(ss,'\0',sizeof(ss));//
for (int j=i;j<=i+len-;j++) ss[j-i]=s[][j];
if (!ok||(ok && strcmp(ss,str)<)) strcpy(str,ss);
ok=true;
}
if (ok) break;
}
if (!ok) printf("no significant commonalities\n");
else printf("%s\n",str);
}
return ;
}
上一篇:LNAMP架构中后端Apache获取用户真实IP地址的2种方法(转)


下一篇:Thinkphp常用的方法和技巧(转)