bzoj 3620: 似乎在梦中见过的样子

n^2的kmp暴力可过；
发现竟不会写kmp了…..

#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=(n);i++)
using namespace std;
const int maxn=15005;
const int inf=0x7f7f7f7f;
char s[maxn];int p[maxn],k,ans=0,n,g[maxn];

int main(){//freopen("in.in","r",stdin);
scanf("%s%d",s+1,&k);n=strlen(s+1);
    rep(i,1,n){
    rep(j,1,n)p[j]=i-1;
    rep(j,i+1,n){
        int t=p[j-1];
        while(t!=i-1 && s[t+1]!=s[j])t=p[t];
        p[j]=s[t+1]==s[j] ? t+1 : i-1;
    }
    rep(j,i+2,n){
        int t=p[j];
        while(2*(t-i+1)>=(j-i+1))t=p[t];
        if(t-i+1>=k)ans++;
    }
    }
    printf("%d",ans);
}