Knuth–Morris–Pratt Illustrated

Re:Knuth–Morris–Pratt Illustrated by Terr_ on Monday April 15, 2024 @11:50PM (#40048188)

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

[ Parent | on HN ]

Re:Knuth–Morris–Pratt Illustrated by byronvickers on Tuesday April 16, 2024 @05:10AM (#40049874)

Thanks 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!

[ Parent | on HN ]

Re:Knuth–Morris–Pratt Illustrated by Terr_ on Tuesday April 16, 2024 @04:51PM (#40057028)

I 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.

[ Parent | on HN ]