阿华田方法是什么？

阿华田方法（Aho-Corasickalgorithm），也称为AC自动机，是一种用于多模式字符串匹配的算法。它可以在一个文本串中同时查找多个关键字，并且能够高效地处理大量的输入数据。

这个算法由AlfredV.Aho和MargaretJ.Corasick发明并发表于1975年的论文《EfficientStringMatching:AnAidtoBibliographicSearch》中。主要应用领域涉及到了词频统计、网络安全等方面。

如何实现阿华田方法？

将所有需要匹配的字符串构建成一棵Trie树，在构造Trie树时，每个节点存储终止状态信息即是否存在打上标记；同时引入失败指针（FailPointer）优化搜索过程：

-对于任意节点v，它对应子串s1s2…**。

-v的fail指针表示从root出发跳到某结点w，则value[w]为s1s2…si(i