NKOJ 4350 （SDOI 2016）生成魔咒（后缀自动机）

发表于 |
字数统计: 623字 | 阅读时长 ≈ 3min

P4350生成魔咒

问题描述

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。

一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。

例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。

最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。

输入格式

第一行一个整数 n。

第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。

1≤n≤100000。用来表示魔咒字符的数字 x 满足 1≤x≤10^9

输出格式

输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量

样例输入

7
1 2 3 3 3 1 2

样例输出

1
3
6
9
12
17
22

此题的关键在于动态维护不同子串个数，考虑后缀自动机。

事实上，考虑一下可以发现后缀自动机在增量法构造过程中，每加入一个字符会增加一些新的子串，而增加的子串个数恰好就是$Max[np]-Max[par[np]]$，证明是显然的，因为新增加的子串必然是以当前字符为结尾的整个串后缀，那么新增的子串就是原来没有的后缀。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#define int long long
#define N 200005
using namespace std;
map<int,int>son[N];
int n,tot=1,rt=1,las=1,Max[N],pra[N],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);
	while(p&&!son[p][t])son[p][t]=np,p=pra[p];
	if(!p)pra[np]=rt;
	else
	{
		q=son[p][t];
		if(Max[q]==Max[p]+1)pra[np]=q;
		else
		{
			nq=NP(Max[p]+1);
			son[nq]=son[q];
			pra[nq]=pra[q];
			pra[q]=pra[np]=nq;
			while(son[p][t]==q)son[p][t]=nq,p=pra[p];
		}
	}
	Ans+=Max[np]-Max[pra[np]];
	las=np;
}
main()
{
	int x;
	scanf("%lld",&n);
	while(n--)
	{
		scanf("%lld",&x);
		Ins(x);printf("%lld\n",Ans);
	}
}