思路

每个起点维护不超过半长的最长Border，A两段之间B非空，同一子串不同拆法只计一次，1.5万长度可二次扫描。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;int k;cin>>s>>k;int n=s.size();vector<int>p(n);long long ans=0;for(int start=0;start+2*k<n;start++){const char*t=s.data()+start;int m=n-start,j=0;p[0]=0;for(int i=1;i<m;i++){int v=p[i-1];while(v&&t[v]!=t[i])v=p[v-1];if(t[v]==t[i])v++;p[i]=v;while(j&&t[j]!=t[i])j=p[j-1];if(t[j]==t[i])j++;while(2*j>=i+1)j=p[j-1];if(j>=k)ans++;}}cout<<ans<<'\n';}