题解 P4070 【[SDOI2016]生成魔咒】
Warriors_Cat
2020-12-29 13:01:13
[题面传送门](https://www.luogu.com.cn/problem/P4070)。
> 题意:问一个字符串的所有前缀的本质不同子串个数。
可以算是一个 SAM 练手题吧,[不会 SAM 先往这边走。](https://www.luogu.com.cn/problem/P3804)
---
### $Solution:$
我们考虑每次把一个节点丢进 SAM 所产生的贡献。
根据 SAM 的性质,每次新增一个节点 $p$,它的贡献实际上就是 $len_p - minlen_p + 1$,又有 $minlen_p = len_{fail_p} + 1$,于是每次多一个节点的时候加上 $len_p - len_{fail_p}$ 即可。
很显然 SAM 是个在线算法,因此可以这么搞。
注意到本题字符集很大,因此需要用 `map` 来存 `nxt` 数组。
over,时间复杂度为 $O(n\log n)$,$\log$ 为 map 的复杂度。
### $Code:$
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repn(i, x, y, z) for(int i = x; i <= y; i += z)
#define pern(i, x, y, z) for(int i = x; i >= y; i -= z)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010;
int n, len[N], fail[N], tail, tot, a[N];
map <int, int> nxt[N]; ll ans;
inline void SAMinit(){ fail[0] = -1; tail = tot = 0; }
inline void SAMadd(int c){
len[++tot] = len[tail] + 1; int p = tail; tail = tot;
for(; p != -1 && !nxt[p][c]; p = fail[p]) nxt[p][c] = tail;
if(p == -1){ fail[tail] = 0; ans += len[tail] - len[fail[tail]]; return; } int q = nxt[p][c];
if(len[q] == len[p] + 1){ fail[tail] = q; ans += len[tail] - len[fail[tail]]; return; }
len[++tot] = len[p] + 1; fail[tot] = fail[q]; nxt[tot] = nxt[q];
for(; p != -1 && nxt[p][c] == q; p = fail[p]) nxt[p][c] = tot;
fail[tail] = fail[q] = tot; ans += len[tail] - len[fail[tail]];
}
inline void mian(){
n = read(); rep(i, 1, n) a[i] = read(); SAMinit();
rep(i, 1, n){ SAMadd(a[i]); printf("%lld\n", ans); }
}
signed main(){ int qwq = 1; while(qwq--) mian(); return 0; }
```