Given a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is a concatenation of each word in L exactly once and without any intervening characters. This substring will occur exactly once in S.

The first line of input specifies L, it will contain between 1 and 100 space-separated words, each between 1 and 10 characters long.

The second line of input specifies S, the line will contain a single word up to 1 million characters long.

The characters in both L and S should be treated as case-sensitive.

Question

Given a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is a concatenation of each word in L exactly once and without any intervening characters.  This substring will occur exactly once in S. 

The first line of input specifies L, it will contain between 1 and 100 space-separated words, each between 1 and 10 characters long. 

The second line of input specifies S, the line will contain a single word up to 1 million characters long. 

The characters in both L and S should be treated as case-sensitive.

g152xx · Answer

Example:
L: "fooo", "barr", "wing", "ding", "wing"
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake"
                 fooowingdingbarrwing
Answer: 13
 
L: "mon", "key"
S: "monkey
    monkey
Answer: 0
 
L: "a", "b", "c", "d", "e"
S: "abcdfecdba"
         ecdba
Answer: 5

mayankdevnani · Answer

http://interviewsutra.com/facebook/given-a-list-of-words-l-that-are-all-the-same-length-and-a-string-s-find-the-starting-position-of-the-substring-of-s-that-is-a-concatenation-of-each-word-in-l-exactly-once-and-without-any-interve.php

g152xx · Answer

@mayankdevnani thanks but doenst have the code on the page. Found here something like mine : http://www.careercup.com/question?id=12332722

turingtest · Answer

Please post this in the computer science section. Thanks.