回文子串的个数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 char s[N],a[N];
 5 int n;
 6 int hw[N];
 7 inline void change(){
 8     s[0]=s[1]=‘#‘;
 9     for(int i=0;i<n;i++){
10         s[i*2+2]=a[i];
11         s[i*2+3]=‘#‘;
12     }
13     n=2*n+2;
14     s[n]=0;
15 }
16 inline void manacher(){
17     int mxr=0,mid;
18     for(int i = 1;i < n ; i ++){
19         if(i < mxr)
20             hw[i] = min ( hw[(mid << 1)-i],hw[mid] + mid - i);
21         else hw[i]=1;
22 
23         while((i + hw[i]<n && (i - hw[i])>0) && s[i+hw[i]]==s[i-hw[i]])
24             ++hw[i];
25         if(i+hw[i]>mxr)
26             mxr=i+hw[i],mid=i;
27     }
28 }
29 int main(){
30     ios::sync_with_stdio(0);
31     cin.tie(0);
32     cout.tie(0);
33     cin>>a;
34     n=strlen(a);
35     change();
36     manacher();
37     int ans=0;
38     for(int i=0;i<n;i++)
39         ans+=hw[i]/2;
40     cout<<ans;
41 }