题解 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}

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