Substring Concatenation Finder

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

More formally, given a string s and a list of words, let each word have length l and let there be n words. Then the total length of the concatenated substring is \( L = l \times n \). You need to find all starting indices i such that the substring s[i : i+L] is a permutation of the concatenation of all the words.

If no such substring exists, output an empty list.

Note: The order of the words in the concatenation does not matter.

inputFormat

The input is given via stdin:

• Line 1: A non-empty string s consisting of lowercase and/or uppercase letters.
• Line 2: An integer n representing the number of words.
• Line 3: If n > 0, a sequence of n words separated by spaces. If n is 0, this line may be empty.

outputFormat

Print to stdout the starting indices (0-indexed) of the substrings that form a concatenation of all words exactly once, separated by a single space. If there is no such substring, output an empty line.

barfoofoobarthefoobarman
3
bar foo the

6 9 12