zstu-3769 数回文子串

思路：用manacher求出每个位置的半径，相加即可。

代码：【rad[i]/2】即i这个位置的回文半径，添加的'#'代表长度为偶数的串。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 const int N=1e5+11;
 6 char s[N],cpy[N<<1];
 7 int rad[N<<1];
 8 void manacher(char *s,int len,int rad[])
 9 {
10     for(int i=1,j=0,k;i<len;i+=k)
11     {
12         while(s[i-j-1]==s[i+j+1])    j++;
13         rad[i]=j;
14         for(k=1;k<=rad[i]&&rad[i-k]!=rad[i]-k;k++)
15             rad[i+k]=min(rad[i]-k,rad[i-k]);
16         j=max(j-k,0);
17     }
18 }
19 void work(char *s,int rad[])
20 {
21     int len=strlen(s);
22     cpy[0]='(',cpy[1]='#';
23     for(int i=0,j=2;i<len;i++,j+=2)
24     {
25         cpy[j]=s[i];
26         cpy[j+1]='#';
27     }
28     cpy[(len=len*2+3)-1]=')';
29     manacher(cpy,len,rad);
30     int ans=0;
31     for(int i=0;i<len;i++)
32         ans+=rad[i]/2;
33     printf("%d
",ans);
34 }
35 int main()
36 {
37     while(scanf("%s",s)!=EOF)
38     {
39         work(s,rad);
40     } 
41     return 0;
42 }