Tang-Dreamoon's Blog

bzoj 3676 回文串

发表于 | 分类于 ， ，

膜拜神犇YZY

　　题目链接：bzoj 3676

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：这道题让我们求出所有回文串的出现次数乘以长度的最大值。对于一个回文串，它的长度很好知道，问题在于回文串的出现次数是多少。网上的诸多题解采用的是回文自动机的做法，然而我们这里介绍一个机智的拓扑排序的方法。我们可以发现如果一个极长的回文串 X 出现了一次，那么 X-2，X-4，X-6……所有的小回文串的出现次数都加一。可是如果直接这样计算的话，复杂度显然是 O(N^2) 的。所以我们考虑把已经出现过的回文串用它们的 Hash 值记录下来。然后不断的由 X 向 X-2 连边，直到 X 在之前已经出现过那么就停止连边，因为剩下的边在之前一定已经连过了。然后运用拓扑排序来计数就可以求出所有的回文串的出现次数了。

　　我思故我在：这一道题之所以没有自己想出来，关键是对马拉车这个算法的理解不到位，没有意识到本质不同的回文串数量不会超过 O(N) 个，所以至多会有 N 个节点。原因是，本质不同的回文串只有可能在马拉车暴力匹配的时候产生，既然每个点只有可能被暴力匹配一次，所以有最多 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int tot=0;
long long base=131;
long long modd=373353751ll;
long long moddd=175379353ll;
char ap[300300];
char map[300300*2];
int lena[300300*2];
long long  hash[300300*2];
long long  hush[300300*2];
long long  jinz[300300*2];
long long  jina[300300*2];
long long p=100003;
int vis[100004][30];
int fa[300300*2];
int rd[300300*2];
long long  size[300300*2];
long long  chan[300300*2];
struct table{
	int fi,se;
};
vector<table> ve[100004];
int biao(int x,int w,int z)
{
	int y=x%p;
	int ans=0;
	for(int i=0;i<ve[y].size();i++)
	{
		if(ve[y][i].fi==x&&ve[y][i].se==w)
		{
			ans=vis[y][i];
			break;
		}
	}
	if(z!=0)
	{
		if(ans==0)
			ve[y].push_back((table){x,w}),vis[y][ve[y].size()-1]=++tot,fa[z]=tot,rd[tot]++;
		else fa[z]=ans,rd[ans]++;
	}
	else
	{
		if(ans==0)
			ve[y].push_back((table){x,w}),vis[y][ve[y].size()-1]=++tot,size[tot]++;
		else size[ans]++;
	}
	return ans;
}
void make()
{
	jinz[0]=1;
	jina[0]=1;
	for(int i=1;i<=600600;i++)
	{
		jinz[i]=jinz[i-1]*base%modd;
		jina[i]=jina[i-1]*base%moddd;
	}
}
void tupo()
{
	queue<int> q;
	for(int i=1;i<=tot;i++)
		if(rd[i]==0) q.push(i);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		if(fa[x]!=0)
		{
			size[fa[x]]+=size[x];
			rd[fa[x]]--;
			if(rd[fa[x]]==0) q.push(fa[x]);
		}
	}
}
int main()
{
	scanf("%s",ap+1);
	int n=strlen(ap+1);
	for(int i=1;i<=n;i++)
	{
		map[i*2-1]='*';
		map[i*2]=ap[i];
	}
	map[n*2+1]='*';
	make();
	for(int i=1;i<=n*2+1;i++)
	{
		hash[i]=(hash[i-1]*base%modd+map[i])%modd;
	}
	for(int i=1;i<=n*2+1;i++)
	{
		hush[i]=(hush[i-1]*base%moddd+map[i])%moddd;
	}
	int now=1;
	lena[1]=0;
	for(int i=2;i<=n*2+1;i++)
	{
		if(i<=now+lena[now])
		{
			int x=now-(i-now);
			if(i+lena[x]<now+lena[now]) lena[i]=lena[x];
			else
			{
				int j=now+lena[now]-i+1;
				while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) j++;
				now=i,lena[i]=j-1;
			}
		}
		else
		{
			int j=1;
			while((i+j)<=(n*2+1)&&(i-j)>=1&&map[i+j]==map[i-j]) j++;
			now=i,lena[i]=j-1;
		}
	}
	for(int i=2;i<=n*2+1;i++)
	{
		if(lena[i]>0)
		{
			int x=(hash[i+lena[i]-1]-hash[i-lena[i]]*jinz[2*lena[i]-1]%modd+modd)%modd;
			int f=(hush[i+lena[i]-1]-hush[i-lena[i]]*jina[2*lena[i]-1]%moddd+moddd)%moddd;
			int whe=biao(x,f,0);
			int y=lena[i]-1;
			int z=(y+1)/2*2;
			if((i%2)==0) z++;
			if(whe==0) chan[tot]=z;
			y-=2;
			while((whe==0)&&y>=0)
			{
				if(y==0&&map[i]=='*') break;
				x=(hash[i+y]-hash[i-y-1]*jinz[2*y+1]%modd+modd)%modd;
				f=(hush[i+y]-hush[i-y-1]*jina[2*y+1]%moddd+moddd)%moddd;
				whe=biao(x,f,tot);
				z=(y+1)/2*2;
				if((i%2)==0) z++;
				if(whe==0) chan[tot]=z;
				y-=2;
			}
		}
	}
	tupo();
	long long  maxa=-1;
	for(int i=1;i<=tot;i++)
		maxa=max(maxa,size[i]*chan[i]);
	cout<<maxa<<endl;
	return 0;
}