http://sdu.acmclub.com/index.php?app=problem_title&id=961&problem_id=23772
题意：给出一个01串，问有多少个子串翻转再取反等于它本身。
题解：老实说这一题，如果深入了解Manacher，这一条就是水题了。首先满足条件的这样的串的特点：1长度一定是偶数2 左右对称的位置之和一定是1，就是一个位置是0另外一个位置是1.这样，如果联系上Manacher的话，求得是最大的回文串，判断时候是对称的位置相等，这里把它换成之和是1就好，另外原来串的位置有加入‘#’，这里可以另外加一个判断，就是遇到这样的字符就直接跳过。然后最重的结果就是长度为偶数那些回文串并且长度大于1，因为这里求出的是最大的长度，所以只要把rad[i]/2就可以得到个数。这里要注意，因为是偶数，所以在匹配的时候只要i只要从奇数位开始就可以了。偶数位不要计算。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define M 1000050 6 using namespace std; 7 char str1[M],str[M*2]; 8 int rad[M]; 9 void Manacher(int *rad, char *str,int n){ 10 int i,mx=0,id; 11 for(i=1;i<n;i+=2){//下标从1开始 12 if(mx>i){ 13 rad[i]=min(rad[2*id-i],mx-i); 14 } 15 else rad[i]=1; 16 for(;(str[i+rad[i]]-'0'+str[i-rad[i]]-'0'==1)||str[i+rad[i]]=='2';rad[i]++){ 17 if(rad[i]+i>mx){ 18 mx=rad[i]+i; 19 id=i; 20 } 21 } 22 // printf("**%d %d ",i,rad[i]); 23 } 24 } 25 int main(){ 26 int nn; 27 long long ans; 28 while(~scanf("%d",&nn)){ 29 scanf("%s",str1); 30 int n=nn*2+2; 31 str[0]='$'; 32 memset(rad,0,sizeof(rad)); 33 for(int i=0;i<=nn;i++){ 34 str[2*i+1]='2'; 35 str[2*i+2]=str1[i]; 36 } 37 Manacher(rad,str,n); 38 ans=0; 39 for(int i=0;i<n;i++) 40 if(rad[i]>1&&rad[i]&1) 41 // printf("%d %d ",i,rad[i]); 42 ans+=(long long)rad[i]/2; 43 printf("%lld ",ans); 44 memset(str,0,sizeof(str)); 45 memset(str1,0,sizeof(str1)); 46 } 47 return 0; 48 }