后缀自动机模板2 统计某一子串出现次数

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

其实就是每个字符串的endpos集的大小,无非就是同长度取max而已

我们注意到,如果一个字符串在st状态中出现,其必在trans决定的后续状态中继续出现。且每次在st状态中新出现的字符串,一定是以转移过来的节点的字符串做前缀的。

所以我们把每个非clone节点的位置的值设为1,clone节点的位置的值设为0,直接用后缀链link构成的DAG上跑拓扑DP就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char ss[maxn];
typedef long long ll;
int len;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],trans[maxn][26],maxlen[maxn];
    queue<int>q;
    vector<int>g[maxn];
    int indeg[maxn];
    ll ans1;
    ll ans[maxn],endpos[maxn];
    int last;
    void init(){
        last = tot = 1;
        return;
    }
    int extend(int ch){
        int x,y,z = ++tot;
        int p = last;
        endpos[z] = 1;
        maxlen[z] = maxlen[last] + 1;
        while(p && !trans[p][ch])
            trans[p][ch] = z,p = link[p];
        if(!p){
            link[z] = 1;
        }
        else{
            x = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                y = ++tot;
                endpos[y] = 0;
                maxlen[y] = maxlen[p] + 1;
                for(int i = 0;i < 26;++i)
                    trans[y][i] = trans[x][i];
                while(p && trans[p][ch] == x){
                    trans[p][ch] = y;
                    p = link[p];
                }
                link[y] = link[x];
                link[z] = link[x] = y;
            }
        }
        last = z;
    }
    void build(){
        for(int i = 1;i <= tot;++i){
            g[i].push_back(link[i]);
            ++indeg[link[i]];
        }
    }
    void calc1(){//本质不同子串数量
        ans1 = 0;
        for(int i = 1;i <= tot;++i){
            ans1 += maxlen[i] - maxlen[link[i]];
        }
    }
    void calc2(){
        build();
        for(int i = 0;i <= tot;++i){
            if(!indeg[i])q.push(i);
        }
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(auto it : g[now]){
                endpos[it] += endpos[now];
                indeg[it]--;
                if(indeg[it] == 0)
                    q.push(it);
            }
        }
        for(int i = 1;i <= tot;++i)
            ans[maxlen[i]] = max(ans[maxlen[i]],endpos[i]);
        for(int i = len - 1;i >= 1;--i){
            ans[i] = max(ans[i],ans[i+1]);
        }
    }
}M;
int main(){
    scanf("%s",ss);
    len = strlen(ss);
    M.init();
    for(int i = 0;i < len;++i){
        M.extend(ss[i]-'a');
    }
    M.calc2();
    for(int i = 1;i <= len;++i){
        printf("%lld\n",M.ans[i]);
    }
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char ss[maxn];
typedef long long ll;
int len;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],trans[maxn][26],maxlen[maxn];
    queue<int>q;
    vector<int>g[maxn];
    int indeg[maxn];
    ll ans1;
    ll ans[maxn],endpos[maxn];
    int last;
    void init(){
        last = tot = 1;
        return;
    }
    int extend(int ch){
        int x,y,z = ++tot;
        int p = last;
        endpos[z] = 1;
        maxlen[z] = maxlen[last] + 1;
        while(p && !trans[p][ch])
            trans[p][ch] = z,p = link[p];
        if(!p){
            link[z] = 1;
        }
        else{
            x = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                y = ++tot;
                endpos[y] = 0;
                maxlen[y] = maxlen[p] + 1;
                for(int i = 0;i < 26;++i)
                    trans[y][i] = trans[x][i];
                while(p && trans[p][ch] == x){
                    trans[p][ch] = y;
                    p = link[p];
                }
                link[y] = link[x];
                link[z] = link[x] = y;
            }
        }
        last = z;
    }
    void build(){
        for(int i = 1;i <= tot;++i){
            g[i].push_back(link[i]);
            ++indeg[link[i]];
        }
    }
    void calc1(){//本质不同子串数量
        ans1 = 0;
        for(int i = 1;i <= tot;++i){
            ans1 += maxlen[i] - maxlen[link[i]];
        }
    }
    void calc2(){
        build();
        for(int i = 0;i <= tot;++i){
            if(!indeg[i])q.push(i);
        }
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(auto it : g[now]){
                endpos[it] += endpos[now];
                indeg[it]--;
                if(indeg[it] == 0)
                    q.push(it);
            }
        }
        for(int i = 1;i <= tot;++i)
            ans[maxlen[i]] = max(ans[maxlen[i]],endpos[i]);
        for(int i = len - 1;i >= 1;--i){
            ans[i] = max(ans[i],ans[i+1]);
        }
    }
}M;
int main(){
    scanf("%s",ss);
    len = strlen(ss);
    M.init();
    for(int i = 0;i < len;++i){
        M.extend(ss[i]-'a');
    }
    M.calc2();
    for(int i = 1;i <= len;++i){
        printf("%lld\n",M.ans[i]);
    }
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00