#include <bits/stdc++.h>
using namespace std;
const int MAXLEN = 15000;
string s;
int k, ans;
int len[MAXLEN + 5];
int len2[MAXLEN + 5];
void getNxt(int pos)
{
	/*
	nxt[0] = 0;
	for (int i = 1; i < s.length(); i++)
	{
		int j = nxt[i - 1];
		while (j != 0 && s[j] != s[i])
			j = nxt[j - 1];
		if (s[j] == s[i])
			j++;
		nxt[i] = j;
	}
	*/
	// 计算 s[pos~] 的 len[]
	// len[] 是公共前后缀，需要正常求，不然会错过
	// len2[] 比较特殊，最长的公共前后缀不超过 k 时存 0。
	// 否则存最短的，
	len[pos] = 0;
	len2[pos] = 0;
	for (int i = pos + 1; i < s.length(); i++)
	{
		int j = len[i - 1];
		while (j != 0 && s[pos + j] != s[i])
			j = len[pos + j - 1];
		if (s[pos + j] == s[i])
			j++;
		len[i] = j;
		if (len2[pos + len[i] - 1] != 0)
			len2[i] = len2[pos + len[i] - 1];
		else if (len[i] >= k)
			len2[i] = len[i];
		else
			len2[i] = 0;
		if (len2[i] != 0 && i - pos + 1 - len2[i] - len2[i] >= 1)
			ans++;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	cin >> k;
	ans = 0;
	for (int i = 0; i < s.length(); i++)
		getNxt(i);
	cout << ans << "\n";
	return 0;
}

考虑到$|s|$只有$1.5e4$, 这里提供一种$O(n^2)$做法, 但是最坏能被卡到$O(n^3)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1.5e4 + 5;
int n, k, ans;
int nxt[N];
string s;
inline void KMP(int l, int r)
{
    // 注意: |A| >= k && |B| >= 1
    if (r - l + 1 < 2 * k + 1)
        return;
    // 如果整个字符串的长度不符合题意直接不做
    nxt[0] = 0;
    for (int i = 1, j = 0; i < r - l + 1; i++)
    {
        int len = i + 1;
        while (j && s[i + l] != s[j + l])
            j = nxt[j - 1];
        if (s[i + l] == s[j + l])
            j++;
        // 标准KMP 由于是区间 需要略微修改一下
        nxt[i] = j;
        // 因为j在后续的循环中仍然要使用 一定一定用别的变量存一下做
        int p = j;
        if (p >= k && len >= 2 * k + 1) // 如果这个点的前缀函数大于k 证明|A|>=k
        {
            while (p && p * 2 >= len) // 但是不能保证有重叠的情况 如果有重叠就往回跳
                p = nxt[p - 1];
            ans += (p >= k); // 最后判断此时是否还能满足条件
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> k;
    n = s.size();
    for (int i = 0; i < n; i++)
        KMP(i, n - 1);
    //由于要枚举每一个子串，我们从头开始做，每次删去最开头的字母，再对当前字符串作KMP
    cout << ans << endl;
}

2023.4.6 $Hacked$ 悲

考虑到在向前跳的时候容易暴力走很多步，于是提前使用$mem$数组记录$|A|$

复杂度$O(n^2)$ 修改后代码如下:

    if (mem[nxt[i] - 1] != 0)
        mem[i] = mem[nxt[i] - 1]; // 如果对称的地方已经求过就直接用
    else if (nxt[i] >= k)
        mem[i] = nxt[i]; // 如果长度大于k证明符合题意
    else
        mem[i] = 0;  // 否则直接记0即可 方便判断
    if (mem[i] != 0 && i >= 2 * mem[i]) // 同样要处理边界条件
        ans++;