【bzoj3620】似乎在梦中见过的样子 KMP

时间:2023-01-07 10:50:19

题目描述

给出一个长度$\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;
}