AC自动机

AC 就是一种多模式字符串匹配算法。多模式匹配算法就是在一个主串中查找多个模式串。

原理

AC自动机算法是构造一个Trie数，然后再添加额外的失配指针。这些额外的失配指针在查找字符串失败的时候进行回退(例如在Trie树中查找单词bef失败后，但是在Trie树中存在bea这个单词，失配指针会指向前缀be), 转向某些前缀分支，免于重复匹配前缀，提高算法效率.

假设现有模式字符串集合： {abd, abdk, abchijn, chnit, ijabdf, ijaij} 构建AC自动机。