#include <cstdio>
#include <cstring>
#define min(a, b) a > b ? b : a
const int maxn = 15e3 + 5, INF = 0x3f3f3f3f;
int k, Next[maxn], Num[maxn], ans;
char str[maxn];
int main() {
scanf("%s %d", str + 1, &k);
int n = strlen(str + 1);
for (int l = 1; l <= n; l++) {
memset(Num, 0x3f, sizeof Num);
Next[1] = 0;
for (int len = 2, j = 0; len <= n - l + 1; len++) {
int r = l + len - 1;
while (j && str[r] != str[l + j]) j = Next[j];
if (str[r] == str[l + j]) j++;
Next[len] = j;
if (j < k) Num[len] = INF;
else Num[len] = min(Num[Next[len]], j);
if (Num[len] * 2 < len) ans++;
}
}
printf("%d\n", ans);
return 0;
}
原文:https://www.cnblogs.com/AlphaWA/p/10780328.html