bzoj 3620 似乎在梦中见过的样子（KMP）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=3620

【题意】

给定一个字符串，统计有多少形如A+B+A的子串，要求A>=K,B>=1。

【思路】

枚举左端点i，对字符串s[i..n]统计答案。

放个指针，然后枚举右端点j，如果指针超过长度一半则沿fail向前找，设指针为k。如果匹配则满足s[i..k]==s[j-k+1..j]，最后判定一下长度限制。

【代码】

 #include<cstdio>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int N = 2e4+;

 int n,K;

 ll ans;

 int f[N];

 char s[N];

 void KMP(char *s) {

     int n=strlen(s+);

     int j=,now=;

     for(int i=;i<=n;i++) {

         while(j&&s[j+]!=s[i]) j=f[j];

         if(s[j+]==s[i]) j++;

         f[i]=j;

         while(now&&s[now+]!=s[i]) now=f[now];

         if(s[now+]==s[i]) now++;

         while(*now>=i) now=f[now];

         if(now>=K) ans++;

     }

 }

 int main()

 {

     scanf("%s%d",s+,&K);

     int n=strlen(s+);

     for(int i=;i<=n;i++) KMP(s+i);

     printf("%lld\n",ans);

     return ;

 }