3 ms·
The Aho-Corasick automaton [0]. You have a bunch of strings, and you want to know if and where they appear in a longer string. You build a search trie from the
by nicwolff 4y ago
The Aho-Corasick automaton [0]. You have a bunch of strings, and you want to know if and where they appear in a longer string. You build a search trie from the strings, but add links back from each node to the node representing the longest suffix of the string it represents that is also in the trie, so you can skip backtracking as you scan, yielding linear time complexity in O(length of string being searched + number of results found).
[0] https://en.wikipedia.org/wiki/Aho–Corasick_algorithm https://en.wikipedia.org/wiki/Aho–Corasick_algorithm
- burntsushi 4y agoThe aho-corasick Rust crate[1] also provides a way to build the automaton in a slightly different way to provide leftmost first or "preference first" match semantics. This matches how popular backtracking regex engines implement alternations of literals, for example. (It also provides leftmost longest semantics, which matches how POSIX regexes implement alternations.) [1]: https://docs.rs/aho-corasick https://docs.rs/aho-corasick