Substring with Concatenation of All Words

You are given a string s and an array of words. Your task is to find all starting indices of substrings in s that are a concatenation of each word in the array exactly once and without any intervening characters. The words can appear in any order in the substring.

More formally, let s be a string and words be an array of n words, each of length m. A valid substring is a concatenation of each word in words exactly once, so its length is m*n. You need to output all starting indices (0-indexed) of such substrings in the string s.

Note: If no such substring exists, print an empty line.

inputFormat

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

1. The first line contains the string s.
2. The second line contains an integer n indicating the number of words.
3. The third line contains n space-separated words.

outputFormat

Print the starting indices of all valid substrings as space-separated integers on a single line to standard output (stdout). If there are no valid substrings, print an empty line.

barfoothefoobarman
2
foo bar

0 9