题解 P2408 【不同子串个数】

# 不同子串个数 [题目传送门](https://www.luogu.com.cn/problem/P2408) ## 思路 来一篇比较不一样的$\text {SAM}$。看到很多$\text {SAM}$都是用的拓扑序之后$\text {dp}$，实际上，我们可以直接动态维护。 考虑增加一个点之后，我们设$\text {maxlen,minlen}$表示这个点表示的字符串的最长长度和最短长度。可以得到的是，每次加入一个一个点答案就会增加$\text {maxlen-minlen+1}$,又因为$\text {minlen=maxlen(fa)+1}$,$\text {fa}$就是指的这个点的后缀连接。所以，每次就会增加$\text {maxlen-maxlen(fa)}$。 实测这种方法会比$dp$快一倍。 ## $\text {Code}$ ```cpp #include <bits/stdc++.h> using namespace std; #define Int register int #define ll long long #define MAXN 200005 template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;} template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);} template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');} int n; char s[MAXN]; int lst = 1,node = 1; int len[MAXN],fa[MAXN],ch[MAXN][26]; ll ans; void Insert (int c){ int f = lst,q = ++ node;lst = q; len[q] = len[f] + 1; while (f && !ch[f][c]) ch[f][c] = q,f = fa[f]; if (!f) fa[q] = 1; else{ int x = ch[f][c]; if (len[x] == len[f] + 1) fa[q] = x; else{ int p = ++ node; fa[p] = fa[x],len[p] = len[f] + 1; memcpy (ch[p],ch[x],sizeof (ch[x])); fa[x] = fa[q] = p; while (f && ch[f][c] == x) ch[f][c] = p,f = fa[f]; } } ans += len[q] - len[fa[q]]; } signed main(){ read (n); scanf ("%s",s + 1); for (Int i = 1;i <= n;++ i) Insert (s[i] - 'a'); write (ans),putchar ('\n'); return 0; } ```