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.

Answer 1

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

Answer 2

i dint get u.....
why is that answer for the second case is zero?
like monkey s got mon and key r8?

Answer 3

One thought, parse the substings in L into a set or the keys of a map, iterate through S, checking for S.substring( iterator, iterator+len( setEntry ) ) to be in the set/map. If found, hand a copy of the set/map, len( setEntry ) and S.substring(iterator) to a checker function that deletes each word as it's found. Success would be an empty set/map.