Getting a string from a list of substrings

Question

I asked to solve the following problem in a programming contest (facebook recruitment)

Input: list of substrings:

{"bar","foo","hi"} //from 1 to 100 sub-strings 

and suggestion:

 "hellothisisfoobarhi" //from 1 to 1000000 character 

Output: 12 // index of the first match in the sentence (foo)

another example:

substring: {"hello", "hello"}

offer: "hiJonIamSayinghihiforYou"

output: 15 // index hi, the second "hi", because the first "hi" is just a trick, sub-sentece is "hi" hi "

one more ex:

substrings: {"hello", "Foo"}

offer: "sayfoohi"

conclusion: 6 // the order does not matter, they just have to be next to each other

Who knows a good algorithm for this problem?

Answer 1

Build a tree of suffixes of a large string - building a tree is O (n), where n is the length of a large string.

Now you can find the location of any of the substrings in O (m) time (where m is the length of the substring), simply by following the substring down the tree - node or sheet, where the key corresponding to the index will be held at the end of the substring in a large string.

Go through many substrings, finding their location in a large line, tracking the minimum index.

Answer 2

Another way is to focus on substrings rather than the main line - http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm