2024-01-17：用go语言，给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = ["ab","cd","ef"]，
那么 "abcdef"， "abefcd"，"cdabef"，
"cdefab"，"efabcd"， 和 "efcdab" 都是串联子串，
"acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联字串在 s 中的开始索引。
你可以以 任意顺序 返回答案。
1 <= s.length <= 10^4，
1 <= words.length <= 5000，
1 <= words[i].length <= 30。
words[i] 和 s 由小写英文字母组成。
输入：s = "barfoothefoobarman", words = ["foo","bar"]。
输出：[0,9]。
来自lc的30. 串联所有单词的子串。
答案2024-01-17：
来自左程云。
大体过程如下：
-
定义一些常量和变量，包括
BASE和MAXN，以及存储结果的切片ans。 -
实现
hashValue函数，用于计算字符串的哈希值。这里使用一个基于索引的简单哈希函数将字符串映射为一个唯一的整数。 -
实现
buildHash函数，用于构建字符串的前缀哈希数组。通过动态规划的方式计算每个位置的哈希值。 -
实现
hashValueRange函数，用于计算子串的哈希值。利用前缀哈希数组，根据子串的起始和结束位置计算哈希值。 -
创建一个哈希表
mapCount用于存储words中每个单词的出现次数。 -
构建字符串
s的前缀哈希数组hash。 -
创建一个数组
pow，用于存储 BASE 的幂次方，便于后续计算子串的哈希值。 -
创建一个滑动窗口
window，用于记录当前窗口中每个单词出现的次数。 -
循环遍历
s中每个起始位置的可能性（即从 0 到wordLen-1）。 -
在每个起始位置，初始化一个变量
debt用于记录还需要凑齐的单词数。 -
在每个起始位置，遍历
words中的单词，依次将其添加到窗口中，并更新debt的值。 -
如果
debt等于 0，表示窗口中已经包含了所有words中的单词，则将当前起始位置加入结果数组ans中。 -
对于每个起始位置，向右移动窗口，同时更新窗口中单词的出现次数。
-
检查窗口中的哈希值和单词出现次数是否符合要求，如果符合则将当前起始位置加入结果数组
ans中。 -
清空滑动窗口
window。 -
返回结果数组
ans。
总的时间复杂度：O(n * m * k)，其中 n 是字符串 s 的长度，m 是 words 的长度，k 是单词的平均长度。
总的额外空间复杂度：O(n)，其中 n 是字符串 s 的长度，主要用于存储哈希表、前缀哈希数组和结果数组。
go完整代码如下：
package main
import (
"fmt"
)
var BASE = 499
var MAXN = 10001
func hashValue(str string) int64 {
if str == "" {
return 0
}
n := len(str)
ans := int64(str[0]-'a') + 1
for j := 1; j < n; j++ {
ans = ans*int64(BASE) + int64(str[j]-'a') + 1
}
return ans
}
func buildHash(str string) []int64 {
hash := make([]int64, len(str))
hash[0] = int64(str[0]-'a') + 1
for j := 1; j < len(str); j++ {
hash[j] = hash[j-1]*int64(BASE) + int64(str[j]-'a') + 1
}
return hash
}
func hashValueRange(l, r int, hash []int64, pow []int64) int64 {
ans := hash[r-1]
if l > 0 {
ans -= hash[l-1] * pow[r-l]
}
return ans
}
func findSubstring(s string, words []string) []int {
var ans []int
if len(s) == 0 || len(words) == 0 {
return ans
}
wordLen := len(words[0])
wordNum := len(words)
allLen := wordLen * wordNum
mapCount := make(map[int64]int)
for _, key := range words {
v := hashValue(key)
mapCount[v]++
}
hash := buildHash(s)
pow := make([]int64, MAXN)
pow[0] = 1
for j := 1; j < MAXN; j++ {
pow[j] = pow[j-1] * int64(BASE)
}
window := make(map[int64]int)
for init := 0; init < wordLen && init+allLen <= len(s); init++ {
debt := wordNum
for l, r, part := init, init+wordLen, 0; part < wordNum; l += wordLen {
cur := hashValueRange(l, r, hash, pow)
window[cur]++
if window[cur] <= mapCount[cur] {
debt--
}
r += wordLen
part++
}
if debt == 0 {
ans = append(ans, init)
}
for l1, r1, l2, r2 := init, init+wordLen, init+allLen, init+allLen+wordLen; r2 <= len(s); l1, r1, l2, r2 = l1+wordLen, r1+wordLen, l2+wordLen, r2+wordLen {
out := hashValueRange(l1, r1, hash, pow)
in := hashValueRange(l2, r2, hash, pow)
window[out]--
if window[out] < mapCount[out] {
debt++
}
window[in]++
if window[in] <= mapCount[in] {
debt--
}
if debt == 0 {
ans = append(ans, r1)
}
}
for key := range window {
delete(window, key)
}
}
return ans
}
func main() {
s := "barfoothefoobarman"
words := []string{"foo", "bar"}
result := findSubstring(s, words)
fmt.Println(result)
}
