【洛谷 P3975】 [TJOI2015]弦论（后缀自动机）

题目链接

建出后缀自动机。

T=0，每个子串算一次，否则每个子串算该子串的\(endpos\)集合大小次。

用\(f[i]\)表示结点\(i\)表示的\(endpos\)集合大小，则\(f[i]\)为其parent tree的子树的\(f\)之和(T=0时，f[i]均为1)。

用\(g[i]\)表示从结点\(i\)出发的子串个数，则\(g[i]\)为\(f[i]\)加上结点\(i\)所有出边的\(g[v]\)之和。

类似平衡树跑第\(k\)小。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#define O(x) cout << #x << "=" << x << endl;

using namespace std;

const int MAXN = 1000010;

struct SAM{

    int ch[26];

    int len, fa;

}sam[MAXN << 1];

int las = 1, cnt = 1, f[MAXN << 1], g[MAXN << 1];

struct Edge{

    int next, to;

}e[MAXN << 1];

int head[MAXN << 1], num;

inline void Add(int from, int to){

    e[++num].to = to; e[num].next = head[from]; head[from] = num;

}

inline void add(int c){

    int p = las; int np = las = ++cnt;

    sam[np].len = sam[p].len + 1; f[cnt] = 1;

    for(; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np;

    if(!p) sam[np].fa = 1;

    else{

        int q = sam[p].ch[c];

        if(sam[q].len == sam[p].len + 1) sam[np].fa = q;

        else{

            int nq = ++cnt; sam[nq] = sam[q];

            sam[nq].len = sam[p].len + 1;

            sam[q].fa = sam[np].fa = nq;

            for(; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq;

        }

    }

}

char a[MAXN];

int t, k;

void dfs(int u){

    for(int i = head[u]; i; i = e[i].next){

        dfs(e[i].to);

        f[u] += f[e[i].to];

    }

}

void Dfs(int u){

    g[u] = f[u];

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

        if(sam[u].ch[i]){

            if(!g[sam[u].ch[i]]) Dfs(sam[u].ch[i]);

            g[u] += g[sam[u].ch[i]];

        }

}

void DFS(int u, int res){

    if(res <= f[u]) return;

    res -= f[u];

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

        if(sam[u].ch[i])

            if(g[sam[u].ch[i]] >= res){

                putchar(i + 'a');

                DFS(sam[u].ch[i], res);

                return;

            }

            else res -= g[sam[u].ch[i]];

    printf("-1\n");

}

int main(){

    scanf("%s", a + 1);

    scanf("%d%d", &t, &k);

    int len = strlen(a + 1);

    for(int i = 1; i <= len; ++i)

       add(a[i] - 'a');

    for(int i = 2; i <= cnt; ++i)

        Add(sam[i].fa, i);

    if(t) dfs(1);

    else for(int i = 2; i <= cnt; ++i) f[i] = 1;

    f[1] = 0;

    Dfs(1); DFS(1, k);

    return 0;

}

巴特西

【洛谷 P3975】 [TJOI2015]弦论（后缀自动机）

最新文章

热门文章