一本通 2.2 练习 3似乎在梦中见过的样子

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