2013长春网赛1005 hdu 4763 Theme Section(kmp应用)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4763

题意:给出一个字符串,问能不能在该串的前中后部找到相同的子串,输出最长的字串的长度。

分析:kmp的next[]数组应用。

next[i]=k表示在位置i之前有k个字符与字符串前k个字符相同,利用这个性质,先求出next[]数组,注意next[len]也要求出来,next[i]就表示字符串的后部与前部相同的长度,这样就只需找有没有中部就可以了。在next[i]到len-next[i]之间找有没有和next[i]相同的值就行了,找到就表示有中部,否则没有,这时i=next[i],然后继续找有没有中部,一直到next[i]==0为止。

之前的做法是错的,因为题目要求前缀,中缀,后缀不能出现重叠,之前的做法会导致3个错误:

1.可能会导致求出来的前缀和中缀重叠导致错误;

2.在next[i]到len-next[i]中间可能出现长度与前缀相同但是字符不一样的字串,比如:aaaaabbbbaaaa,这样用之前的做法会得出错误的答案;

3.如果前缀和中缀是连续的,那么next[len]就有可能是前缀和中缀的总长度和了,这样也会错误。

所以不能仅仅依靠next[]数组来求解

正确的做法是:

在next[i]到len-next[i]之间用kmp匹配前缀,如果匹配成功,则说明能找到中部,否则不能,i=next[i]然后继续查找中部,直到next[i]==0即可.

根据next[]数组的性质,循环的次数不超过3次,因为如果后部和前部不相同的话,next[i]==0,这样很快就可以跳出循环了。

还可以加个优化:前中后部字串的长度最多为len/3,如果next[i]>len/3的话就可以直接跳过查找中部,进入下一次循环了。但是优化不大,因为循环次数非常少。

AC代码:

 #include<cstdio>
#include<cstring>
const int N=+;
int next[N];
char s[N],c[N],d[N];
void get_next(char s[])
{
int len=strlen(s);
int i=;
int j=-;
next[]=-;
while(i<=len) //注意要==
{
if(j==-||s[i]==s[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int kmp(char t[],char s[])
{
int i,j,k,m,n;
m=strlen(s);
n=strlen(t);
i=j=k=;
while(i<m&&j<n)
{
if(j==- || t[j]==s[i])
{
i++;
j++;
}
else
j=next[j];
}
if(j>=n)
return ;
else
return ;
}
int main()
{
int t,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
get_next(s);
int len=strlen(s);
int i=next[len];
int flag=;
while(i>)
{
while(i>len/)
i=next[i];
if(i<=)
break;
/********************************
错误解法:
for(j=i;j<=len-i;j++) //找中部
if(next[j]==i)
{
flag=1;
break;
}
********************************/
for(k=,j=;j<i;j++)
c[k++]=s[j];
c[k]='\0';
for(k=;j<len-i;j++)
d[k++]=s[j];
d[k]='\0';
flag=kmp(c,d);
if(flag==) //找到了
break;
else
i=next[i]; //找不到,循环继续
}
if(flag)
printf("%d\n",i);
else
printf("0\n");
}
return ;
}
上一篇:HDU 4763 Theme Section


下一篇:HDU 4763 Theme Section(KMP+枚举公共前后缀)