Substring with Concatenation of All Words

You are given a string \(s\) and a list of words, all having the same length. Your task is to find all starting indices in \(s\) where a concatenation of each word in the list appears exactly once and without any intervening characters. In other words, you must find all substrings in \(s\) that are formed by concatenating all the given words in any order.

For example, if \(s = \texttt{barfoothefoobarman}\) and \(words = [\texttt{foo}, \texttt{bar}]\), then the answer is \( [0, 9] \) because the substrings \(\texttt{barfoo}\) starting at index 0 and \(\texttt{foobar}\) starting at index 9 are both valid concatenations.

The length of each valid concatenation equals \(L \times n\), where \(L\) is the length of each word and \(n\) is the number of words. Use appropriate algorithms to check each possible starting index efficiently.

inputFormat

The input is provided via standard input (stdin) in the following format:

1. The first line contains the string \(s\).
2. The second line contains an integer \(n\) representing the number of words.
3. The third line contains \(n\) words separated by spaces. All words are guaranteed to have the same length.

outputFormat

Output to standard output (stdout) the starting indices (0-indexed) of all substrings in \(s\) that form a valid concatenation of each word exactly once. The indices should be printed in increasing order and separated by a single space. If no valid substring exists, output an empty line.

barfoothefoobarman
2
foo bar

0 9