题目描述

给定一个字符串 $s$ 和一个字符串数组 $words$。 $words$ 中所有字符串 长度相同。

$s$ 中的 串联子串 是指一个包含  $words$ 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 $words = ["ab","cd","ef"]$， 那么 $"abcdef"$， $"abefcd"$，$"cdabef"$， $"cdefab"$，$"efabcd"$， 和 $"efcdab"$ 都是串联子串。 $"acdbef"$ 不是串联子串，因为他不是任何 $words$ 排列的连接。

返回所有串联子串在 $s$ 中的开始索引。你要以 从小到大的顺序 返回答案。

输入格式

第一行一个字符串 $s$;

第二行一个整数 $m$，表示 $words$中字符串数量；

接下来 $m$ 行，每行一个字符串。

输出格式

一行，若干个空格分开的整数，表示所有串联子串在 $s$ 中的开始索引，从小到大排序。如果没有请输出 -1；

样例

示例 1：

barfoothefoobarman
2
foo
bar

0 9

解释： 因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。

子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。

子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。

示例 2：

wordgoodgoodgoodbestword
4
word
good
best
word

-1

解释： 因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。

s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。

所以我们返回 -1。

示例 3：

barfoofoobarthefoobarman
3
bar
foo
the

6 9 12

解释： 因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。

子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。

子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。

子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

• $1 <= s.length <= 10^4$
• $1 <= words.length <= 5000$
• $1 <= words[i].length <= 30$
• $words[i]$ 和 $s$ 由小写英文字母组成

SOURCE

30. 串联所有单词的子串