Find all (english word) substrings of a given string

This is an interview question: Find all (english word) substrings of a given string. (every = every, ever, very).

Obviously, we can loop over all substrings and check each one against an English dictionary, organized as a set. I believe the dictionary is small enough to fit the RAM. How to organize the dictionary ? As for as I remember, the original spell command loaded the words file in a bitmap, represented a set of words hash values. I would start from that.

Another solution is a trie built from the dictionary. Using the trie we can loop over all string characters and check the trie for each character. I guess the complexity of this solution would be the same in the worst case (O(n^2))

Does it make 开发者_JAVA技巧sense? Would you suggest other solutions?

The Aho-Corasick string matching algorithm which "constructs a finite state machine that resembles a trie with additional links between the various internal nodes."
But everything considered the "build a trie from the English dictionary and do a simultaneous search on it for all suffixes of the given string" should be pretty good for an interview.

I'm not sure a Trie will work easily to match sub words that begin in the middle of the string.

Another solution with a similar concept is to use a state machine or regular expression. the regular expression is just word1|word2|.... I'm not sure if standard regular expression engines can handle an expression covering the whole English language, but it shouldn't be hard to build the equivalent state machine given the dictionary.

Once the regular expression is compiled \ the state machine is built the complexity of analyzing a specific string is O(n)

The first solution can be refined to have a different hash map for each word length (to reduce collisions) but other than that I can't think of anything significantly better.