SAM 复习

s_r_f · 2021-03-07 11:47:05 · 个人记录

没有什么理由不拼尽全力了

SAM板子

struct SuffixAutomaton{
    map<char,int>ch[V]; int cnt,ed,len[V],fa[V],size[V];
    inline void init(){
        for (int i = 1; i <= cnt; ++i) len[i] = fa[i] = size[i] = 0,ch[i].clear();
        cnt = ed = 1;
    }
    inline void extend(char c){
        int p = ed,np = ++cnt; size[np] = 1,len[np] = len[ed] + 1;
        while (p && !ch[p].count(c)) ch[p][c] = np,p = fa[p];
        if (!p) fa[np] = 1;
        else{
            int q = ch[p][c];
            if (len[q] == len[p] + 1) fa[np] = q;
            else{
                int nq = ++cnt;
                fa[nq] = fa[q],ch[nq] = ch[q],len[nq] = len[p]+1;
                fa[np] = fa[q] = nq;
                while (ch[p].count(c) && ch[p][c] == q) ch[p][c] = nq,p = fa[p];
            }
        }
        ed = np;
    }
    int c[N],a[V];
    inline void Sort(){
        int i;
        for (i = 0; i <= len[ed]; ++i) c[i] = 0;
        for (i = 1; i <= cnt; ++i) ++c[len[i]];
        for (i = 1; i <= len[ed]; ++i) c[i] += c[i-1];
        for (i = 1; i <= cnt; ++i) a[c[len[i]]--] = i;
    }
}SAM;

题目

CF802I Fake News (hard)

用来练手的板子题.

建出 SAM 之后每个点的贡献显然是 (len_x-len_{fa_x})siz^2_x , 直接计算即可 , \Theta(\sum|S|)