对于一个0/1字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。比如00001111和010101就是反对称的，而1001就不是。
现在给出一个长度为n的0/1字符串，求它有多少个子串是反对称的，注意这里相同的子串出现在不同的位置会被重复计算。
8
11001011
7
对于100%的数据，1≤n≤500000。
思路：显然符合条件的字串长度为偶数，否则中间那位取反后不可能与原串相同。
枚举前半部分最后一个位置（1~n-1），二分长度hash即可。
#include<bits/stdc++.h> #include<queue> #include<cstdio> #include<cstring> #include<cmath> #define ull unsigned long long; #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) const int maxn = 5e5 + 5; using namespace std; char str[maxn]; int n, a[maxn], b[maxn], gt; long long tot; int ha[maxn], hb[maxn], base[maxn]; int funa(int l, int r) { return ha[r] - ha[l - 1] * base[r - l + 1]; } int funb(int l, int r) { return hb[l] - hb[r + 1] * base[r - l + 1]; } int main(){ cin >> n; base[0] = 1; scanf("%s", str+1); REP(i, 1, n)a[i] = str[i] - ‘0‘, b[i] = a[i] ^ 1; REP(i, 1, n)ha[i] = ha[i - 1] * 131 + a[i], base[i] = base[i - 1] * 131; PER(i,n,1)hb[i] = hb[i+1] * 131 + b[i]; for (int i = 1; i < n; i++) { int l = 1, r= min(i, n - i), mid; gt = 0; while (l <= r) { int mid = (l + r) / 2; if(funa(i-mid+1,i+mid)==funb(i-mid+1,i+mid))gt=mid,l=mid+1; else r = mid - 1; } tot += gt; } cout<<tot<<endl; }
原文：https://www.cnblogs.com/czy-power/p/10357495.html