题意描述

求给定的字符串的子串集合中为“反对串”的个数。

反对串的定义为，将这个字符串 \(0\) 和 \(1\) 取反后，再将整个串反过来和原串一样，就称作“反对串”。

算法分析

一开始想法是字符串 Hash \(O(n^2)\)，不出意外 T 到飞起。

发现“反对串”的定义类似回文串，于是想到 Manacher，发现可行。

让我们先来探究一下“反对串”的几个性质：

若串 \(S(l,r)\) 为反对串，那么串 \(S'(l+1,r-1)\) 也为反对串。

若串 \(S(l,r)\) 为反对串且 \(a_{l-1}\neq a_{r+1}\)，那么串 \(S'(l-1,r+1)\) 为反对串。

反对串的长度比为偶数。

有了这几个简单的性质就可以直接套用 Manacher 模板了。

利用性质 \(2\) 类似地求出最大长度。

不过基于性质 \(3\)，只需要求偶数长度的串即可。（在 Manacher 上的表现为只拓展 '#'）

然后利用性质 \(1\)，易得答案为 \(\sum_{i=1}^{n}\frac{p_i}{2}(i\ mod\ 2=1)\)。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cmath>

#define N 500010

using namespace std;

long long n,len=2,p[N<<1];

char a[N],s[N<<1];

int main(){

	scanf("%d",&n);

	scanf("%s",a+1);

	s[0]='$',s[1]='#';

	for(int i=1;i<=n;i++)

		s[len++]=a[i],s[len++]='#';

	s[len]='\0';

	long long id,mx=0,ans=0;

	for(int i=1;i<len;i+=2){

		if(i<mx)

			p[i]=min(p[2*id-i],mx-i);

		else

			p[i]=1;

		while((s[i-p[i]]=='#' && s[i+p[i]]=='#') || (s[i-p[i]]-'0'+s[i+p[i]]-'0')==1)

			p[i]++;

		if(mx<i+p[i])

			id=i,mx=i+p[i];

	}

	for(int i=1;i<len;i+=2)

		ans+=p[i]-1;

	printf("%lld\n",ans/2);

	return 0;

}

完结撒❀。

巴特西

Antisymmetry

题意描述

算法分析

代码实现

最新文章

热门文章