「BZOJ3620」似乎在梦中见过的样子

Description

「Madoka,不要相信 QB!」伴随着 Homura 的失望地喊叫,Madoka 与 QB 签订了契约。

这是 Modoka 的一个噩梦,也同时是上个轮回中所发生的事。为了使这一次 Madoka 不再与 QB 签订契约,Homura 决定在刚到学校的第一天就解决 QB。然而,QB 也是有许多替身的(但在第八话中的剧情显示它也有可能是无限重生的),不过,意志坚定的 Homura 是不会放弃的——她决定消灭所有可能是 QB 的东西。现在,她已感受到附近的状态,并且把它转化为一个长度为 nn 的字符串交给了学 OI 的你。

现在你从她的话中知道,所有形似于 A+B+AA+B+A 的字串都是 QB 或它的替身,且 Ak,B1|A|\ge k,|B|\ge 1 (位置不同其他性质相同的子串算不同子串,位置相同但拆分不同的子串算同一子串),然后你必须尽快告诉 Homura 这个答案——QB 以及它的替身的数量。

注:对于一个字符串 SSS|S| 表示 SS 的长度。

Input

第一行一个字符串 SS,第二行一个数 kk

Output

仅一行一个数 ans\text{ans},表示 QB 以及它的替身的数量。

Sample Input

样例输入 1

1
2
aaaaa
1

样例输入 2

1
2
abcabcabc
2

Sample Output

样例输出 1

1
6

样例输出 2

1
8

HINT

对于全部数据,1S1.5×104,1k1001\le |S|\le 1.5\times 10^4,1\le k\le 100,且字符集为所有小写字母。

Solution

暴力跳nxtnxt数组,如果出现一次符合条件直接break。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2e4;
char s[N];
int n, m, nxt[N];

int main() {
cin>>(s + 1);
n = strlen(s + 1);
m = read();
ll ans = 0;
for(int T = 1; T <= n; ++T) {
int res = 0;
nxt[T] = T - 1;
int j = T - 1;
for(int i = T + 1; i <= n; ++i) {
while(j != T - 1 && s[j + 1] != s[i]) j = nxt[j];
if(s[j + 1] == s[i]) ++j;
nxt[i] = j;
}
for(int i = T; i <= n; ++i) {
j = nxt[i];
while(j != T - 1 && (j - T + 1) >= m) {
if((j - T + 1) * 2 < i - T + 1) {
++ans, ++res;
break;
}
j = nxt[j];
}
}
}
writeln(ans);
return 0;
}