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 jkdistructureds trusyssystemoon 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–Pr att 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