BZOJ 2084 Poi2010 Antisymmetry Manacher算法

题目大意：给定一个长度为n的01串，问有多少个子串满足翻转并取反后和原来一样

定义0=1,0≠0,1≠1,跑Manacher即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 500500
using namespace std;
int n;
char s[M];
long long Manacher(char str[],int n)
{
	static char s[M<<1];
	static int f[M<<1];
	int i;
	for(s[0]='$',s[1]='#',i=1;i<=n;i++)
		s[i<<1]=str[i],s[i<<1|1]='#';
	n=n<<1|1;
	int mx=1,id=1;
	long long re=0;
	for(i=1;i<=n;i++)
	{
		f[i]=max(min(f[id+id-i],mx-i),0);
		while( s[i+f[i]]=='#'&&s[i-f[i]]=='#' || min(s[i+f[i]],s[i-f[i]])=='0'&&max(s[i+f[i]],s[i-f[i]])=='1' )
			f[i]++;
		if(i+f[i]>mx)
			mx=i+f[i],id=i;
		re+=f[i]>>1;
	}
	return re;
}
int main()
{
	cin>>n;
	scanf("%s",s+1);
	printf("%lld\n",Manacher(s,n));
}

BZOJ 2084 Poi2010 Antisymmetry Manacher算法

原文：http://blog.csdn.net/popoqqq/article/details/44039921