[bzoj3998][TJOI2015]弦论-后缀自动机

Brief Description

给定一个字符串, 您需要求出他的严格k小子串或非严格k小子串.

Algorithm Design

考察使用后缀自动机.

首先原串建SAM, 然后如果考察每个状态代表的子串的出现次数. 可以知道, 在parent树上某个节点的出现次数就是他的所有儿子的出现次数之和. 所以, 我们可以按照len基数排序, 然后根据这种拓扑序把出现次数计算出来, 同时, 我们也统计出了以某个节点为根的子树的出现次数总和.

有了每个状态的出现次数之后, 我们运行后缀自动机, 每次选择字典序最小的转移, 如果转移到达的状态所为根的子树的总出现次数大于k, 我们就可以输出这个字符, 同时k-=sum[trans[x][i]].

Code

#include <cstdio>

#include <cstring>

const int maxn = 5e5 + 1e2;

const int maxm = maxn << 1;

int N, T, k;

char str[maxn];

struct Suffix_Automaton {

  int rt, last, trans[maxm][26], fa[maxm], sz, len[maxm], cnt[maxm];

  int v[maxn], q[maxm], sum[maxm];

  void init() {

    sz = 0;

    rt = last = ++sz;

  }

  void insert(int x) {

    int p = last, np = last = ++sz;

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

    cnt[np] = 1;

    while (!trans[p][x] && p) {

      trans[p][x] = np;

      p = fa[p];

    }

    if (!p) {

      fa[np] = 1;

    } else {

      int q = trans[p][x];

      if (len[q] == len[p] + 1) {

        fa[np] = q;

      } else {

        int nq = ++sz;

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

        memcpy(trans[nq], trans[q], sizeof(trans[q]));

        fa[nq] = fa[q];

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

        while (trans[p][x] == q) {

          trans[p][x] = nq;

          p = fa[p];

        }

      }

    }

    return;

  }

  void pre() {

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

      v[len[i]]++;

    for (int i = 1; i <= ::N; i++)

      v[i] += v[i - 1];

    for (int i = sz; i; i--)

      q[v[len[i]]--] = i;

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

      int t = q[i];

      if (T == 1)

        cnt[fa[t]] += cnt[t];

      else

        cnt[t] = 1;

    }

    cnt[1] = 0;

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

      int t = q[i];

      sum[t] = cnt[t];

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

        sum[t] += sum[trans[t][j]];

    }

  }

  void dfs(int x, int k) {

    if (k <= cnt[x])

      return;

    k -= cnt[x];

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

      if (int t = trans[x][i]) {

        if (k <= sum[t]) {

          putchar(i + 'a');

          dfs(t, k);

          return;

        }

        k -= sum[t];

      }

  }

} sam;

int main() {

#ifndef ONLINE_JUDGE

  freopen("input", "r", stdin);

#endif

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

  N = strlen(str + 1);

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

  sam.init();

  for (int i = 1; i <= N; i++) {

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

  }

  sam.pre();

  if (k > sam.sum[1])

    printf("-1\n");

  else

    sam.dfs(1, k);

  return 0;

}