「ural2040」Palindromes and Super Abilities 2 - 回文自动机

题目大意

    给出一个字符串，从前往后一个一个字符插入，查询每次增加了多少个不同的回文串。

---

题目分析

根据回文自动机的空间证明，不难发现答案只可能为$0$或$1$。
每次查询形成的最长回文是否已出现过即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=5000005;

struct Palindsome_Automaton {
	int child[maxn][2];
	int n,size,last,s[maxn],len[maxn],next[maxn];
	Palindsome_Automaton() {
		size=-1;
		newnode(0); //even
		newnode(-1); //odd
		last=n=0;
		s[0]=-1;
		next[0]=next[1]=1;
	}
	int newnode(int v) {
		int now=++size;
		len[now]=v;
		return now;
	}
	int insert(int data) {
		s[++n]=data;
		int p=last;
		while(s[n-len[p]-1]!=s[n])p=next[p];
		bool bj=1;
		if(!child[p][data]) {
			int now=newnode(len[p]+2),q=next[p];
			while(s[n-len[q]-1]!=s[n])q=next[q];
			next[now]=child[q][data];
			child[p][data]=now;
		} else bj=0;
		last=child[p][data];
		return bj;
	}
	void build(string s) {
		for(auto x:s)printf("%d",insert(x-'a'));
	}
} pam;

char s[maxn];

int main() {
	scanf("%s",s);
	pam.build(s);
	return 0;
}