首先,你需要知道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;
}