后缀自动机之统计不同子串个数

柔情只为你懂 2021-11-24 02:02 265阅读 0赞

### 题目背景 ###

因为NOI被虐傻了，蒟蒻的YJQ准备来学习一下字符串，于是它碰到了这样一道题：

### 题目描述 ###

给你一个长为N的字符串，求不同的子串的个数

我们定义两个子串不同，当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样。

子串的定义：原字符串中连续的一段字符组成的字符串

### 输入格式 ###

第一行一个整数N

接下来一行N个字符表示给出的字符串

### 输出格式 ###

一行一个整数，表示不一样的子串个数

### 输入输出样例 ###

**输入 \#1**复制

5
    aabaa

**输出 \#1**复制

**输入 \#2**复制

3
    aba

**输出 \#2**复制

### 说明/提示 ###

请使用64位整数来进行输出

（具体来说，C++和C选手请使用long long 类型，pascal选手请使用Int64）

由于输入文件过大，请使用 高效的读入方法（具体的，c++和c选手请不要使用cin，pascal选手不需要管）

对于30%的数据，N\\le 1000N≤1000

对于100%的数据，N\\le 10^5N≤105

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int MAXN = 1000010;
    struct SAM{
        int ch[26];
        int len, fa;
    }sam[MAXN << 1];
    int las = 1, cnt = 1;
    long long f[MAXN << 1];
    inline void add(int c){
        int p = las; int np = las = ++cnt;
        sam[np].len = sam[p].len + 1;
        for(; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np;
        if(!p) sam[np].fa = 1;
        else{
            int q = sam[p].ch[c];
            if(sam[q].len == sam[p].len + 1) sam[np].fa = q;
            else{
                int nq = ++cnt; sam[nq] = sam[q];
                sam[nq].len = sam[p].len + 1;
                sam[q].fa = sam[np].fa = nq;
                for(; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq;
            }
        }
    }
    char a[MAXN];
    void dfs(int u){
        f[u] = 1;
        for(int i = 0; i < 26; ++i)
            if(sam[u].ch[i]){
                if(!f[sam[u].ch[i]])
                    dfs(sam[u].ch[i]);
                f[u] += f[sam[u].ch[i]];
            }
    }
    int len;
    int main(){
        scanf("%d", &len);
        scanf("%s", a + 1);
        for(int i = 1; i <= len; ++i)
           add(a[i] - 'a');
        dfs(1);
        printf("%lld\n", f[1] - 1);
        return 0;
    }