SP7258 SUBLEX - Lexicographical Substring Search

给定一个字符串，求本质不同排名第k小的子串

Solution

后缀自动机上每条路径对应一个本质不同的子串

按照 TRANS 图的拓扑序，DP 计算出每个点发出多少条路径

（注意区别 TRANS 图的拓扑序和后缀链接的拓扑序）

然后暴力 26 分询问即可

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2000005;

struct Suffix_Automata {

    int maxlen[Maxn], trans[Maxn][26], link[Maxn], Size, Last;

    int t[Maxn], a[Maxn], cnt[Maxn], f[Maxn];

    Suffix_Automata() { Size = Last = 1; }

    inline void Extend(int id) {

        int cur = (++ Size), p;

        maxlen[cur] = maxlen[Last] + 1;

        cnt[cur] = 1;

        for (p = Last; p && !trans[p][id]; p = link[p]) trans[p][id] = cur;

        if (!p) link[cur] = 1;

        else {

            int q = trans[p][id];

            if (maxlen[q] == maxlen[p] + 1) link[cur] = q;

            else {

                int clone = (++ Size);

                maxlen[clone] = maxlen[p] + 1;

                for(int i=0;i<26;i++) trans[clone][i] = trans[q][i];

                link[clone] = link[q];

                for (; p && trans[p][id] == q; p = link[p]) trans[p][id] = clone;

                link[cur] = link[q] = clone;

            }

        }

        Last = cur;

    }

    void CalcEndposSize() {

        memset(t, 0, sizeof t);

        for(int i=1; i<=Size; i++) t[maxlen[i]]++;

        for(int i=1; i<=Size; i++) t[i]+=t[i-1];

        for(int i=1; i<=Size; i++) a[t[maxlen[i]]--]=i;

        /*for(int i=Size; i>=1; --i) cnt[link[a[i]]]+=cnt[a[i]];

        cnt[1] = 0;*/

    }

    void DFS(int p) {

        for(int i=0;i<26;i++) {

            if(trans[p][i]) {

                if(f[trans[p][i]]==0) DFS(trans[p][i]);

                f[p]+=f[trans[p][i]];

            }

        }

        f[p]+=cnt[p];

    }

    void Go(int p,int k) {

        k-=cnt[p];

        for(int i=0;i<26 && k>0;i++) {

            if(trans[p][i]) {

                if(f[trans[p][i]]>=k) {

                    cout<<(char)(i+'a');

                    Go(trans[p][i],k);

                    return;

                }

                else {

                    k-=f[trans[p][i]];

                }

            }

        }

    }

} sam;

int main() {

    ios::sync_with_stdio(false);

    string str;

    cin>>str;

    int t,k;

    for(int i=0;i<str.length();i++)

        sam.Extend(str[i]-'a');

    sam.CalcEndposSize();

    for(int i=2; i<=sam.Size; i++)

        sam.cnt[i] = 1;

    sam.DFS(1);

    cin>>t;

    while(t--) {

        cin>>k;

        sam.Go(1,k);

        cout<<endl;

    }

}

巴特西

SP7258 SUBLEX - Lexicographical Substring Search - 后缀自动机,dp

Solution

最新文章

热门文章