Aho-Corasick法の追加

[noss3885]

複数文字列探索アルゴリズム。Trie木からオートマトンを構築する。

文字の種類数をk、辞書の文字列の総和をN、入力文字列の長さをMとして

• 有限オートマトンの構築 O(kN)
• 検索 O(N+M+マッチ数)

参考資料

• https://ikatakos.com/pot/programming_algorithm/string_search
• https://naoya-2.hatenadiary.org/entry/20090405/aho_corasick
• https://github.com/kth-competitive-programming/kactl/blob/main/kactl.pdf
• https://firiexp.github.io/library/datastructure/ahocorasick.cpp

テスト問題

• https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257
• https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2212