[TJOI2015]弦论（后缀自动机）

题意：

对给定字符串\(s\)，求其第\(k\)小子串，重复串被计入以及不被计入这两种情况都需考虑。

思路：

首先构建后缀自动机，之后就考虑在后缀自动机上\(dp\)。

我们知道如果要考虑重复串，那么就会与一个结点的\(endpos\)集合的大小有关，对于一条边\((u,v)\)，如果结点\(u\)的\(endpos\)集合大小为\(x\)，那么就说明从\(u\)出发到达\(v\)，会多出\(x\)种选择。

如果不考虑重复串，直接强制集合大小为\(1\)即可。

之后逆着拓扑序\(dp\)就行，求出从每个结点出发的子串个数。

最后求第\(k\)小的时候，有一些细节需要注意一下，比如从\(u\)到\(v\)，\(k\)应该减去\(|endpos(v)|\)，因为现在的字符串会有\(|endpos(v)|\)个。

感觉后缀自动机好神奇...好多的性质以及用法...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;

struct node{

    int ch[26];

    int len, fa;

    node(){memset(ch, 0, sizeof(ch)), len = 0;}

}dian[N];

int last = 1, tot = 1;

ll f[N], sum[N];

int n, k, op;

char s[N];

int c[N], a[N];

void add(int c) {

    int p = last;

    int np = last = ++tot;

    dian[np].len = dian[p].len + 1;

    f[np] = 1;

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

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

    else {

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

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

        else {

            int nq = ++tot; dian[nq] = dian[q];

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

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

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

        }

    }

}

void dfs(int u) {

    if(k <= 0) return;

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

        int v = dian[u].ch[i];

        if(k > sum[v]) k -= sum[v];

        else {

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

            k -= f[v];

            dfs(v);

            return;

        }

    }

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> s + 1 >> op >> k;

    int n = strlen(s + 1);

    for(int i = 1; i <= n; i++) add(s[i] - 'a');

    for(int i = 1; i <= tot; i++) c[dian[i].len]++;

    for(int i = 1; i <= tot; i++) c[i] += c[i - 1];

    for(int i = 1; i <= tot; i++) a[c[dian[i].len]--] = i;

    for(int i = tot; i; i--) {

        if(op) f[dian[a[i]].fa] += f[a[i]];

        else f[a[i]] = 1;

    }

    f[1] = 0;

//长度从大到小，逆着拓扑序

//每个结点的next指针指向的点长度肯定不小于它

    for(int i = tot; i >= 1; i--) {

        sum[a[i]] = f[a[i]];

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

            int v = dian[a[i]].ch[j];

            if(v) sum[a[i]] += sum[v];

        }

    }

    if(sum[1] < k) cout << -1;

    else dfs(1);

    return 0;

}

巴特西

[TJOI2015]弦论（后缀自动机）

最新文章

热门文章