Search Algorithm

[Hamzatbee]

Write an algorithm to perform one of the following tasks,
* “Word Search”: Given a string of letters, identify all substrings that create one of five given words. For example, if the words (arguments) are: structure; such; system; blue; red, then the string jkdistructuredstrusyssystemoon contains the first, third and fifth words, once each.

[jkmyoung]

This seems relatively straight forward. You could brute force it.

You could use a modified Rabin-Karp search algorithm to achieve a single pass (relatively), keeping multiple hash values depending on length.

You could use multiple passes of the Knuth–Morris–Pratt search algorithm, one for each word, or modify it somehow.

Actually, Boyer-Moore would probably work better, compared to Knuth-Morris, but not to Rabin-Karp.

[patjones]

This is fun stuff. I read up on the Boyer-Moore algorithm recently, and thought it was pretty cool that the longer the string to be found is, the more efficient the algorithm becomes! It sounds counter-intuitive on it's face, but makes perfect sense when you really look at how it works and try out an example or two.

Pat