这篇博客写的非常清晰
https://zhuanlan.zhihu.com/p/549242325
给定一个字符串,问有多少个以 k,f,c 结尾的回文子串。
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e6+5;
int n,sum;
ll len[maxn],cnt[128],a[maxn];
string s;
int main(){cin>>n;cin>>s;string p="&|";for(int i=0;i<n;i++)p+=s[i],p+='|';int length=p.size();int mid=1,Rmid=1;for(int i=1;i<length;i++){if(i<Rmid)len[i]=min(len[2*mid-i],len[mid]+mid-i);else len[i]=1;while(p[i-len[i]]==p[i+len[i]])len[i]++;if(i+len[i]>Rmid){Rmid=i+len[i];mid=i;}}for(int i=1;i<length;i++)a[i]++,a[i+len[i]]--;for(int i=1;i<length;i++){sum+=a[i];cnt[p[i]]+=sum;}cout<<cnt['k']<<" "<<cnt['f']<<" "<<cnt['c']<<endl;return 0;
}