20200723 SCOI模拟T2（后缀自动机）

T2

思路：
对于 $n=1$n=1，建出后缀自动机，求子串个数
输出方案直接 DFS 转移

考虑正解，对每个串建后缀自动机，考虑失配后的转移
默认优先选靠前的串
在第 i 个后缀自动机上失配，这时可以选 $i-n$i−n 的串
于是找到 $i-n$i−n 中第一个含失配字符的后缀自动机，然后继续匹配

代码：

#include <bits/stdc++.h>
using namespace std;
#define re register
namespace IO {
inline char ch() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int in() {
  int s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
}  // namespace IO
using namespace IO;

const int A = 3e6 + 5;
const int mod = 1e9 + 7;
int n;
int to[200];
char rev[4] = {'A', 'C', 'G', 'T'};
char nw[A];
int rt[A];
struct SAM {
  int len, f;
  int nex[4];
} tr[4 * A];
int las, tot;

inline void insert(int now, int x) {
  int cur = ++tot;
  tr[cur].len = tr[las].len + 1;
  int p = las;
  while (p && !tr[p].nex[x]) {
    tr[p].nex[x] = cur;
    p = tr[p].f;
  }
  if (!p)
    tr[cur].f = rt[now];
  else {
    int q = tr[p].nex[x];
    if (tr[p].len + 1 == tr[q].len)
      tr[cur].f = q;
    else {
      int cn = ++tot;
      tr[cn] = tr[q];
      tr[cn].len = tr[p].len + 1;
      tr[cur].f = tr[q].f = cn;
      while (p && tr[p].nex[x] == q) {
        tr[p].nex[x] = cn;
        p = tr[p].f;
      }
    }
  }
  las = cur;
  return;
}

int node[A], len;
int res = 0;
inline int add(int x, int y) { return x + y > mod ? x + y - mod : x + y; }
inline void Add(int &x, int y) { x = add(x, y); }

inline void print() {
  for (int i = 1; i <= len; i++) putchar(rev[node[i]]);
  puts("");
  return;
}

inline void DFS(int now, int x, int pos) {
  if (pos) print();
  Add(res, 1);
  for (int i = 0; i < 4; i++) {
    if (tr[x].nex[i]) {
      node[++len] = i;
      DFS(now, tr[x].nex[i], pos);
      len--;
    } else {
      for (int j = now + 1; j <= n; j++)
        if (tr[rt[j]].nex[i]) {
          node[++len] = i;
          DFS(j, tr[rt[j]].nex[i], pos);
          len--;
          break;
        }
    }
  }
  return;
}

signed main() {
  to['A'] = 0, to['C'] = 1, to['G'] = 2, to['T'] = 3;
  n = in();
  for (int i = 1; i <= n; i++) {
    las = rt[i] = ++tot;
    scanf("%s", nw + 1);
    int k = strlen(nw + 1);
    for (int j = 1; j <= k; j++) insert(i, to[nw[j]]);
  }
  int pos = in();
  if (!pos)
    DFS(1, 1, 0);
  else
    DFS(1, 1, 1);
  printf("%d\n", res);
  return 0;
}