Aho-Corasick 自动机

【题目描述】

给定字符串 $S_0, \dots, S_{N-1}$，每个字符串都由小写英文字母组成。请按下面的描述输出由这些字符串构建出的 Trie 的信息。

• 记 $P_{i,j}$ 为 $S_i$ 的长度为 $j$ 的前缀（其中 $0 \leq j \leq |S_i|$）。
• 定义集合 $P$ 为 $P=\lbrace P_{i,j}\mid 0\leq i<N, 0\leq j\leq |S_i|\rbrace$。设 $n = |P|$。
• $(S_0, \dots, S_{N-1})$ 的 Trie 是一棵包含 $n$ 个顶点的树，顶点与 $P$ 中的元素一一对应。 Trie 中的每个顶点 $v$ 对应某个 $\mathrm{str}(v) \in P$。
  • 当选定的 $(i, j)$ 满足 $\mathrm{str}(v) = P_{i,j}$ 时，按 $(i, j)$ 的字典序为各顶点分配编号 $0, 1, \dots, n-1$，其中 $i$ 取最小。特别地，$\mathrm{str}(0)$ 为空串。
• 对每个顶点 $v$（$1 \leq v < n$），记 $p_v$ 为其父亲顶点的编号。也就是说，$p_v$ 是删去 $\mathrm{str}(v)$ 的最后一个字符后所得字符串对应的顶点的编号。
• 对每个顶点 $v$（$1 \leq v \leq n$），记 $s_v$ 为失配指针（suffix link）指向的顶点编号。也就是说，$s_v$ 是 $\mathrm{str}(v)$ 的属于 $P$ 且比 $\mathrm{str}(v)$ 短的后缀中最长者的顶点编号。

请输出 $n$ 的值，并对每个顶点 $v$（$1 \leq v < n$）输出 $p_v$ 和 $s_v$。此外，对每个 $i = 0, 1, \dots, N-1$，输出 $S_i$ 所对应的顶点的编号。

【输入】

$N$
$S_0$
$\vdots$
$S_{N-1}$

【输出】

$n$
$p_1$ $s_1$
$\vdots$
$p_{n-1}$ $s_{n-1}$
$v_0$ $\ldots$ $v_{N-1}$

【输入样例】

4
b
a
c
a

【输出样例】

4
0 0
0 0
0 0
1 2 3 2

【输入样例2】

3
b
a
ab

【输出样例2】

4
0 0
0 0
2 1
1 2 3

【输入样例3】

1
abcabcaba

【输出样例3】

10
0 0
1 0
2 0
3 1
4 2
5 3
6 4
7 5
8 1
9

【输入样例4】

5
aaa
a
aa
aaaaa
a

【输出样例4】

6
0 0
1 1
2 2
3 3
4 4
3 1 2 5 1

【数据范围】

• $1 \leq N \leq 1000000$
• $1 \leq |S_i| \leq 1000000$
• $1 \leq \sum_{0\leq i<N}|S_i| \leq 1000000$
• $S$ 的每个字符均为小写英文字母。

【来源】

Library Checker（yosupo06） aho_corasick