NKOJ 2844 （APIO 2014）回文串（Manacher+后缀自动机+倍增/回文树）

发表于 |
字数统计: 976字 | 阅读时长 ≈ 5min

P2844【APIO2014】回文串

问题描述

考虑一个只包含小写英文字母的字符串s。我们定义s的一个字串t的“出现价值”为t在s中出现的次数乘以t的长度。请求出s的所有回文子串中的最大“出现价值”。

输入格式

输入只有一行，为一个只包含小写字母的非空字符串s。

输出格式

输出一个整数，为最大的回文子串价值。

样例输入1：

abacaba

样例输入2：

www

样例输出1：

7

样例输出2：

4

首先，此题是回文树模板题。

然后当然可以用朴素做法解决。

由于要查找回文串，考虑Manacher，然后需要查找回文串的出现次数，考虑后缀自动机。

显然的做法是在Manacher过程中，每找到一个回文串，就在自动机上从根开始跑，查找他的出现次数。

注意到事实上同样的回文串不需要多次运算，那么在Manacher过程中只需要在每次超出Max进行拓展时在自动机上查找即可。由于最多拓展n次，那么最多只需要查找n次。

但这样显然要超时，考虑优化查找速度，注意到每个串在自动机上都对应到了一个节点上，而parent树上该串必然是子节点串的后缀，那么考虑在parent树上倍增查找。

只需要在构建自动机的时候记录下每个字符为结尾，对应的节点编号，然后建完后每次从该结尾处倍增往上跳即可。查找复杂度$log_2{n}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 666666
using namespace std;
char s[N],A[N];
int n,rad[N],pos,MAX;
int tot=1,rt=1,las=1,R[N],Max[N],pra[N][22],son[N][26],v[N],S=19;
int TOT,LA[N],NE[N],EN[N];
long long Ans;
int NP(int x)
{
	Max[++tot]=x;
	return tot;
}
void Ins(int t)
{
	int p=las,q,np,nq;
	np=NP(Max[p]+1);v[np]=1;
	while(p&&!son[p][t])son[p][t]=np,p=pra[p][0];
	if(!p)pra[np][0]=rt;
	else
	{
		q=son[p][t];
		if(Max[q]==Max[p]+1)pra[np][0]=q;
		else
		{
			nq=NP(Max[p]+1);
			memcpy(son[nq],son[q],sizeof(son[q]));
			pra[nq][0]=pra[q][0];
			pra[q][0]=pra[np][0]=nq;
			while(son[p][t]==q)son[p][t]=nq,p=pra[p][0];
		}
	}
	las=np;
}
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x)
{
	int i,y;
	for(i=1;i<=S;i++)pra[x][i]=pra[pra[x][i-1]][i-1];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];DFS(y);
		v[x]+=v[y];
	}
}
int Find(int k,int t)
{
	int i,p=R[k];
	for(i=S;i>=0;i--)if(Max[pra[p][i]]>=t)p=pra[p][i];
	return p;
}
void Manacher()
{
	int i,j,k,p;
	MAX=0;Ans=0;pos=0;
	for(i=1;i<=n;i++)
	{
		if(i>MAX)rad[i]=1;
		else rad[i]=min(MAX-i+1,rad[pos*2-i]);
		while(i-rad[i]>0&&i+rad[i]<=n&&A[i-rad[i]]==A[i+rad[i]])
		{
			rad[i]++;
			k=i+rad[i]-2;
			if(A[k]!='%')
			{
				p=Find(k,rad[i]-1);
				Ans=max(Ans,1ll*v[p]*(1ll*rad[i]-1ll));
			}
		}
		if(i+rad[i]-1>MAX)MAX=i+rad[i]-1,pos=i;
	}
	printf("%lld\n",Ans);
}
int main_main()
{
	int i;
	scanf("%s",s);
	n=strlen(s);
	for(i=0;i<n;i++)
	{
		A[i+1<<1]=s[i];
		A[(i+1<<1)-1]=A[(i+1<<1)+1]='%';
		Ins(s[i]-'a');R[i+1<<1]=las;
	}
	for(i=1;i<=tot;i++)ADD(pra[i][0],i);
	n=n<<1|1;DFS(rt);Manacher();
}
const int main_stack=16;
char my_stack[128<<20];
int main() {
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");  
  main_main();
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
  return 0;
}