『Manacher算法』Antisymmetry

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

对于一个 01 字符串，如果将这个字符串 0 和 1 取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。比如 00001111 和 010101 就是反对称的，而 1001 就不是。 现在给出一个长度为 n 的 01 字符串，求它有多少个子串是反对称的，注意这里相同的子串出现在不同的位置会被重复计算

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

显然，反对称串一定是偶数。

我们发现，如果将等号转化为不等号，那么反对称串就是一个回文串。

因此我们就跑manacher算法，把等于号改成不等于号即可。

但是我们要注意，我们在Manacher算法中会添加$字符，而不是以$为中心的p数组都要赋值为0，避免状态的非法转移。

代码如下：

#include <cstdio>
#include <string.h>
#include <iostream>#define int long longusing namespace std;
const int N = 8e6;int n;
int p[N];
char s[N], a[N];bool check(int i,int j)
{
    return a[i] == '$' && a[j] == '$' || a[i] - '0' + a[j] - '0' == 1;
}void Manacher(int n)
{
    int mx = 0, id = 0;for (int i=1;i<=n*2+1;i+=2){
    p[i] = i < mx ? min(p[id*2-i],mx-i) : 1;while (check(i-p[i],i+p[i])) p[i] ++;if (i + p[i] > mx) mx = i + p[i], id = i;}return;
}signed main(void)
{
    cin>>n>>s+1;a[0] = 'F';a[1] = '$';for (int i=1;i<=n;++i){
    a[i*2] = s[i];a[i*2+1] = '$';}a[n*2+2] = '^';Manacher(n*2+1);int ans = 0;for (int i=1;i<=n*2+1;++i) 	if (a[i] == '$') ans += p[i]/2;cout<<ans<<endl; return 0;
}