Substring with Concatenation of All Words

You are given a string s and an array of words. All the words are of the same length.

Your task is to find all starting indices in s where a substring is formed by the concatenation of each word in the array exactly once and without any intervening characters. The words can appear in any permutation order.

For example, if s = "barfoothefoobarman" and words = ["foo", "bar"], then the output should be [0, 9] since the substrings starting at indices 0 and 9 form "barfoo" and "foobar", respectively.

If no such concatenation exists, output an empty result.

All formulas (if any) use the LaTeX format. For instance, the total length of the concatenated substring can be represented as \(total\_len = word\_len \times word\_count\).

inputFormat

The input is read from standard input (stdin) in the following format:

• The first line contains the string s.
• The second line contains an integer n, which is the number of words.
• The third line contains n words separated by spaces.

outputFormat

Output to standard output (stdout) a single line containing the starting indices (in ascending order) of all substrings in s that are a valid concatenation of all words. The indices should be separated by a single space. If there are no such substrings, output an empty line.

barfoothefoobarman
2
foo bar

0 9