HanLP — Aho-Corasick DoubleArrayTire 算法 ACDAT – 基于双数组字典树的AC自动机

ACDAT的基本原理是替换
AC自动机 的goto表，也可看作为一棵双数组字典树的每个状态（下标）附上额外的信息。上节提到，
AC自动机 的goto表就是字典树，只不过
AC自动机 比字典树多了output 表和fail表。那么ACDAT的构建原理就是为每个状态（base[i]和check[i]）构建output[i][]和fail[i]。具体说来，分为3步。