Substring with Concatenation of All Words

You are given a string s and a list of words. All words in the list have 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 list exactly once and without any intervening characters.

Let \( m \) be the length of each word and \( k \) be the number of words. Then, the substring you are looking for has a total length of \( m \times k \). The words can appear in any order. If there is no such substring, output an empty line.

Note: If either the string s is empty or the words list is empty, then the answer is empty.

inputFormat

The input is read from stdin and consists of:

• A string s on the first line.
• An integer n on the second line representing the number of words.
• If n > 0, a third line containing n space-separated words.

outputFormat

Output to stdout a single line with the starting indices (in ascending order) of all substrings in s that form a concatenation of all the words exactly once, separated by a single space. If there is no valid substring, output an empty line.

barfoothefoobarman
2
foo bar

0 9