2 ms·
Another fun one is the Aho-Corasick algorithm [0] which is great (i.e. more efficient) when you have multiple different target strings you want to find and you
by Terr_ 3y ago
Another fun one is the Aho-Corasick algorithm [0] which is great (i.e. more efficient) when you have multiple different target strings you want to find and you don't want to do multiple scans of the document.
Like KMP, it involves a preliminary step of analyzing the search term(s), and from them it builds a directed graph representing rules for what to do while consuming the stream of document-characters.
To find all occurrences, it's something like O(document_length + all_target_words_combined_length + number_of_hits) .
[0] https://en.wikipedia.org/wiki/Aho-Corasick_algorithm https://en.wikipedia.org/wiki/Aho-Corasick_algorithm
- byronvickers 3y agoThanks for this - I need to solve exactly this problem on a toy project I've been working on; you've saved me the time to hunt down the appropriate algorithm!
- Terr_ 3y agoI hope it helps, but if you are just looking for text strings, you might want to benchmark your local regex libraries first. Among other optimizations, they might use that algorithm under the hood for long (foo|bar|baz|...) expressions.