kmp模板题。
虽然不知道为什么，但是大家都说n^2可以过。
于是直接n^2暴力，每个位置开头跑一遍kmp，也就是暴力枚举每个子串看是否合法。
以i结尾的子串合法满足存在一个nxt使nxt>=k&&i-nxt+1>tp；
十分暴力，我也不知道为什么可过，
//Achen
#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<vector> #include<queue> #include<cmath> #include<ctime>
const int N=15007; typedef long long LL; using namespace std; int n,kk,nxt[N]; LL ans; char ss[N],s[N]; template<typename T> void read(T &x) { T f=1; x=0; char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; } int main() { scanf("%s",ss); read(kk); n=strlen(ss); for(int l=0;l+2*kk<n;l++) { int len=0; for(int i=l;i<n;i++) s[len++]=ss[i]; for(int i=1,k=0;i<len;i++) { while(k&&s[i]!=s[k]) k=nxt[k-1]; if(s[i]==s[k]) k++; nxt[i]=k; int tp=nxt[i]; while(tp>=kk&&(i-tp+1)<=tp) tp=nxt[tp-1]; if(tp>=kk&&(i-tp+1)>tp) ans++; } } printf("%lld\n",ans); return 0; }