题解 P4070 【[SDOI2016]生成魔咒】

[题面传送门](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; } ```