考虑到$|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++;