题意:对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串.比如00001111和010101就是反对称的，1001就不是.现在给出一个长度为N的01字符串，求它有多少个子串是反对称的.(n<=500000.)
分析:仔细分析一波"反对称字符串",其实它是对称的,是'1'和'0'相对,而不是回文的'1'和'1'相对.但是因为字符串中只有'0'或者'1',所以我们还是可以用做找回文子串的方法来做,只是相等改成不等即可.
马拉车算法无疑是很优秀的一种方法了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1000005;
char s[N],a[N];int f[N];
int main(){
int n=read();scanf("%s",s+1);
int tot=0;a[++tot]='~';a[++tot]='|';
for(int i=1;i<=n;++i){
a[++tot]=s[i];
a[++tot]='|';
}
int maxr=0,mid=0;ll ans=0;
for(int i=2;i<=tot;i+=2){//每次只以隔板为中心向两边找
if(i<maxr)f[i]=min(f[(mid<<1)-i],maxr-i);
else f[i]=1;
while((a[i-f[i]]=='1'&&a[i+f[i]]=='0')||(a[i-f[i]]=='0'&&a[i+f[i]]=='1')||(a[i-f[i]]=='|'&&a[i+f[i]]=='|'))++f[i];
//枚举出所有的三种合法情况
if(f[i]+i>maxr)maxr=f[i]+i,mid=i;
ans=ans+(f[i]>>1);//除以2是把隔板产生的贡献除掉了
}
printf("%lld
",ans);
return 0;
}