BZOJ3998 弦论【SAM】k小子串

BZOJ3998 弦论

给一个字符串，问其第\(K\)小字串是什么

两种形式

1.不同起始位置的相同串只算一次

2.不同起始位置的相同串各算一次

首先建\(SAM\)

所有串的数量就是\(SAM\)中的从起始点开始的路径数量，所以可以先在\(SAM\)上\(dp\)出来从所有节点开始的子串数量，然后递归找就好了

\(dp\)的转移为\(dp[u] = cnt[u] + \sum_{v \in children} dp[v]\)

对于第一种，每个节点的\(cnt\)为\(1\)，对于第二种形式，每个节点的\(cnt\)为其\(right\)集合的大小

所以第二种情况下要计算出每个状态的\(right\)集合的大小

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+7;

typedef long long int LL;

char s[MAXN];

int t,K,n;

struct SAM{

    int link[MAXN],len[MAXN],ch[MAXN][26],last,tot;

    LL f[MAXN],cnt[MAXN];

    vector<int> G[MAXN];

    SAM(){ link[0] = -1; last = tot = len[0] = 0; }

    void extend(char chr){

        int c = chr - 'a';

        int np = ++tot, p = last;

        cnt[np] = 1; len[np] = len[last] + 1;

        while(p!=-1 and !ch[p][c]){

            ch[p][c] = np;

            p = link[p];

        }

        if(p==-1) link[np] = 0;

        else{

            int q = ch[p][c];

            if(len[p]+1==len[q]) link[np] = q;

            else{

                int clone = ++tot;

                link[clone] = link[q];

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

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

                link[q] = link[np] = clone;

                while(p!=-1 and ch[p][c]==q){

                    ch[p][c] = clone;

                    p = link[p];

                }

            }

        }

        last = np;

    }

    void calsubstring(int u = 0){

        f[u] = cnt[u];

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

            if(!ch[u][c]) continue;

            if(!f[ch[u][c]]) calsubstring(ch[u][c]);

            f[u] += f[ch[u][c]];

        }

    }

    void build(){ for(int i = 1; i <= tot; i++) G[link[i]].push_back(i); dfs(0); }

    void dfs(int u){

        for(int i = 0; i < (int)G[u].size(); i++){

            int v = G[u][i];

            dfs(v); cnt[u] += cnt[v];

        }

    }

    void _kth(int u, string &str, int k){

        if(k<=cnt[u]) return;

        k -= cnt[u];

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

            if(!ch[u][i]) continue;

            if(f[ch[u][i]]>=k){

                str.append(1,char(i+'a'));

                _kth(ch[u][i],str,k);

                return;

            }

            else k -= f[ch[u][i]];

        }

    }

    string kth(int k){

        if(f[0]<k) return string("-1");

        string str;

        _kth(0,str,k);

        return str;

    }

}sam;

int main(){

    scanf("%s %d %d",s,&t,&K);

    n = strlen(s);

    for(int i = 0; i < n; i++) sam.extend(s[i]);

    if(t==1) sam.build();

    else fill(sam.cnt,sam.cnt+MAXN,1);

    sam.cnt[0] = 0;

    sam.calsubstring();

    printf("%s\n",sam.kth(K).c_str());

    return 0;

}

巴特西

BZOJ3998 弦论【SAM】k小子串

最新文章

热门文章

巴特西

BZOJ3998 弦论 【SAM】k小子串

最新文章

热门文章

BZOJ3998 弦论【SAM】k小子串