首先,你需要知道n方可以过!!!!!!!!!!!!!!!!!! 其次就是神仙暴力 枚举每一个左端点(搞到最后一个) 1:往常kmp搞一搞
{ 当处理到右端点(i)时进行了一次kmp(匹配)的j就是左端点到i(右端点)的前后缀长度(j)
令len=右端点-左端点+1,则当2*j>len,显然这个j是不符合要求的
我们注意到,next[j]同样也是这个区间内的前后缀长度且仅仅次于j,
那么不规范的运用数学归纳法,对于区间内的前后缀长度集合可以表示为{j,next[j],next[next[j].............}
那么整个框架就建好了------------------------- (这个题这么水为什么我看了一天的题解从中午12点看到晚上9点才看懂(一定是我太弱了))
}
贴上loj(5000+m)的代码
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; char a[15005]; int k,n,p[15005],st=0; int pre(char a[]){ for(int i=2,j=0;a[i];i++){ while(a[i]!=a[j+1]&&j)j=p[j]; j+=(a[i]==a[j+1]); p[i]=j; int t=j; while(t*2>=i&&t)t=p[t]; if(t>=k)st++; } } int main(){ scanf("%s",a+1); scanf("%d",&k); n=strlen(a+1); for(int i=0;i<n;i++) pre(a+i); cout<<st<<endl; }