Last update: February 24, 2024 Translated From: e-maxx.ru The Aho-Corasick algorithm allows us to quickly search for multiple patterns in a text. The set of pattern strings is also called a dictionary. We will denote the total length of its constituent strings by $m$ and the size of the alphabet by $k$. The algorithm constructs a finite state automaton based on a trie in $O(m k)$ time and then uses it to process the text. The algorithm was proposed by Alfred Aho and Margaret Corasick in 1975. Co...