题目描述
给出一个长度$\le 15000$的字符串，求满足形似于$A+B+A$（$len(A)\ge k,len(B)\ge 1$）的子串数量。
输入
第一行一个字符串,第二行一个数 k
输出
仅一行一个数 ans,表示 QB 以及它的替身的数量
样例输入
aaaaa
1
样例输出
6
题解
KMP
竟然还有$n^2$过15000的题。。。
由于$len(A)$的限制是$\le k$，而$len(B)$的限制是$\le 1$。因此对于一个子串，找出满足$len(B)\ge 1$条件的$len$最大的$A$。
即找出$len(A)*2<L$的最长的公共前后缀A。
枚举子串的左端点的话，问题就和 动物园 类似，但是需要线性做法，于是特意学了一下那道题的正解。
求next数组的过程相同，在求next的同时直接处理出满足条件的最长前驱后继。具体方法与求next相同，维护一个上一位置的指针，当不满足下一个字符相同，或当长度大于等于一半时k=next[k]即可。最坏总时间复杂度也是$O(L)$的。
求出以后判断最大长度是否大于$k$即可。
时间复杂度为$O(n^2)$，由于常数小可以通过。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[15010];
int next[15010] , p;
int calc(char *s , int n)
{
int i , j , k , ans = 0;
next[0] = -1;
for(i = 1 , j = k = -1 ; i <= n ; i ++ )
{
while(~j && s[j] != s[i - 1]) j = next[j];
next[i] = ++j;
while(~k && (s[k] != s[i - 1] || (k + 1) << 1 >= i)) k = next[k];
if(++k >= p) ans ++ ;
}
return ans;
}
int main()
{
int n , i , ans = 0;
scanf("%s%d" , s , &p) , n = strlen(s);
for(i = 0 ; i < n ; i ++ ) ans += calc(s + i , n - i);
printf("%d\n" , ans);
return 0;
}