BZOJ2342[Shoi2011]双倍回文——回文自动机

一时失言乱红尘 2022-01-05 15:07 146阅读 0赞

## 题目描述 ##

![1_287_29.jpg][]

## 输入 ##

输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。

## 输出 ##

输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。

## 样例输入 ##

16  
ggabaabaabaaball

## 样例输出 ##

## 提示 ##

N<=500000

题意就是要求找到一个最长的回文串满足它的一个回文后缀长度是它的一半，也就是在回文自动机的$fail$树上找到一个所代表的回文串的长度为$4$的倍数的点使它有一个祖先所代表的的回文串的长度是它的一半。直接$dfs$整棵$fail$树，用桶存一下长度为偶数的点即可。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    char s[500010];
    int fail[500010];
    int tr[500010][26];
    int len[500010];
    int n,p,q;
    int last;
    int cnt[500010];
    int head[500010];
    int tot;
    int num;
    int to[500010];
    int next[500010];
    int ans;
    void add(int x,int y)
    {
    	next[++tot]=head[x];
    	head[x]=tot;
    	to[tot]=y;
    }
    int build(int x)
    {
    	len[++num]=x;
    	return num;
    }
    int getfail(int x,int n)
    {
    	while(s[n-len[x]-1]!=s[n])
    	{
    		x=fail[x];
    	}
    	return x;
    }
    void dfs(int x)
    {
    	 if(len[x]%2==0)
    	 {
    	 	cnt[len[x]]++;
    	 }
    	 if(len[x]%4==0&&cnt[len[x]/2])
    	 {
    	 	ans=max(ans,len[x]);
    	 }
    	 for(int i=head[x];i;i=next[i])
    	 {
    	 	dfs(to[i]);
    	 }
    	 cnt[len[x]]--;
    }
    int main()
    {
    	scanf("%d",&n);
    	scanf("%s",s+1);
    	s[0]=-1,fail[0]=1,last=0;
    	len[0]=0,len[1]=-1,num=1;
    	for(int i=1;i<=n;i++)
    	{
    		int x=s[i]-'a';
    		p=getfail(last,i);
    		if(!tr[p][x])
    		{
    			q=build(len[p]+2);
    			fail[q]=tr[getfail(fail[p],i)][x];
    			tr[p][x]=q;
    		}
    		last=tr[p][x];
    	}
    	for(int i=1;i<=num;i++)
    	{
    		add(fail[i],i);
    	}
    	dfs(0);
    	printf("%d",ans);
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10416893.html

[1_287_29.jpg]: https://lydsy.com/JudgeOnline/upload/201111/1%287%29.jpg