HihoCoder – 1445 后缀自动机二·重复旋律5 后缀自动机

后缀自动机二·重复旋律5

Source

HihoCoder - 1445

My Solution

题意：统计字符串中不同子串的个数。

后缀自动机

这题是后缀自动机基础题，直接使用SAM上的pre树， sigma{val[np] - val[pre[np]]}

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 2*1e6 + 8;

string s;
struct SAM{
    int ch[MAXN][26], pre[MAXN], val[MAXN], endpos[MAXN];
    int last, tot;
    void init(){
        last = tot = 0;
        memset(ch[0], -1, sizeof ch[0]);
        pre[0] = -1; val[0] = 0;
    }
    int extend(int c, int ind){
        int p = last, np = ++tot;
        val[np] = val[p] + 1; endpos[np] = ind;
        memset(ch[np], -1, sizeof ch[np]);
        while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p];
        if(p == -1) pre[np] = 0;
        else{
            int q = ch[p][c];
            if(val[q] != val[p] + 1){
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                val[nq] = val[p] + 1;
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
            }
            else pre[np] = q;
        }
        last = np;
        return val[np] - val[pre[np]];
    }
    /*
    vector sons[2*MAXN];
    void build_the_tree(){
        for(int i = 1; i <= tot; i++){ sons[pre[i]].push_back(i); } } */ } sam; int main() { #ifdef LOCAL freopen("21.in", "r", stdin); //freopen("21.out", "w", stdout); int T = 2; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, i; LL sum =0; cin >> s;
    n = s.size();
    sam.init();
    for(i = 0; i < n; i++) sum += sam.extend(s[i] - 'a', i+1);
    cout << sum << endl;;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx