BZOJ4516【SHOI2016】生成魔咒 <后缀自动机>

Problem

【SHOI2016】生成魔咒

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $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$ 共有多少种生成魔咒。

Input

第一行一个整数 $n$。
第二行 $n$ 个数，第 $i$ 个数表示第 $i$ 次操作加入的魔咒字符
$1\le n\le100000$，用来表示魔咒字符的数字 $x$ 满足 $1\le x\le10^9$

Output

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

Sample Input

7
1 2 3 3 3 1 2

Sample Output

1
3
6
9
12
17
22

Source

鸣谢Menci上传

标签：后缀自动机

Solution

后缀自动机的模板题。

按题意增量构建后缀自动机，考虑每次新增的一位能构成多少新串，贡献计入答案。

对于每次新增的结点$np$，若其在$parent$树上的父亲为$par$，那么前面有若干条路走到$par$从而得到的字符串与其走到$np$得到的字符串相同。由于走到$par$的字符串个数是$len_{par}$，走到$np$的字符串个数是$len_{np}$。因此新增字符串个数是$len_{np}-len_{par}$。维护即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mii map<int,int>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, rt, sz, lst;    lnt ans;
struct node {mii ch; int len, par;} SAM[(MAX_N<<1)+5];
int newnode(int _len) {SAM[++sz].len = _len; return sz;}
void init() {sz = 0, rt = lst = newnode(0);}
void insert(int c) {
    int p = lst, np = newnode(SAM[p].len+1);	lst = np;
    for (; p && !SAM[p].ch[c]; p = SAM[p].par) SAM[p].ch[c] = np;
    if (!p) {SAM[np].par = rt; return;}	int q = SAM[p].ch[c];
    if (SAM[q].len == SAM[p].len+1) {SAM[np].par = q; return;}
    int nq = newnode(SAM[p].len+1); SAM[nq].ch = SAM[q].ch;
    SAM[nq].par = SAM[q].par, SAM[q].par = SAM[np].par = nq;
    for (; p && SAM[p].ch[c] == q; p = SAM[p].par) SAM[p].ch[c] = nq;
}
void upd() {ans += SAM[lst].len-SAM[SAM[lst].par].len;}
int main() {
    read(n), init();
    for (int i = 0, x; i < n; i++)
        read(x), insert(x), upd(), printf("%lld\n", ans);
    return 0;
}