P5496 【模板】回文自动机（PAM）

做一下强制在线处理即可

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int trans[500500][26],len[500500],s[500500],fail[500500],last,n,Nodecnt,cnt[500500];

char S[500500];

int New_state(int _len){

	len[Nodecnt]=_len;

	return Nodecnt++;

}

int find(int t,int o){

	while(s[t-len[o]-1]!=s[t])

		o=fail[o];

	return o;

}

void add_len(int n){

	int cur=find(n,last);

	if(!trans[cur][s[n]]){

		int t=New_state(len[cur]+2);

		fail[t]=trans[find(n,fail[cur])][s[n]];

		cnt[t]=cnt[fail[t]]+1;

		trans[cur][s[n]]=t;

	}

	last=trans[cur][s[n]];

}

int main(){

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

	s[0]=-1;

	New_state(0);

	fail[0]=1;

	New_state(-1);

	fail[1]=1;

	last=0;

	n=strlen(S+1);

	int ans=0;

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

		s[i]=(S[i]-97+ans)%26;

		add_len(i);

		ans=cnt[last];

		printf("%d ",ans);

	}

	return 0;

}

巴特西

P5496 【模板】回文自动机（PAM）

最新文章

热门文章