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

Problem

【SHOI2016】生成魔咒

Description

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 , 拼凑起来形成一个魔咒串。
一个魔咒串的非空字串被称为魔咒串的生成魔咒。例如时，它的生成魔咒有 ,,,, 五种。时，它的生成魔咒有 ,, 三种。
最初为空串。共进行次操作，每次操作是在的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串共有多少种生成魔咒。

Input

第一行一个整数。
第二行个数，第个数表示第次操作加入的魔咒字符
，用来表示魔咒字符的数字满足

Output

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

Sample Input

1 2	7 1 2 3 3 3 1 2

Sample Output

Source

鸣谢Menci上传

标签：后缀自动机

Solution

后缀自动机的模板题。

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

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

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;
}