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

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

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

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["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 <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

本题要求在字符串 s 中找到所有包含字符串数组 words 中所有单词的串联子串的起始索引，words 中单词的顺序可以任意排列，但必须紧挨着出现在子串中。

步骤1：问题分析

• s 是一个字符串，words 是一个包含多个字符串的数组，这些字符串的长度相同。
• 我们需要在字符串 s 中找到所有子串，这些子串由 words 中的单词全部串联而成。
• 使用滑动窗口方法来高效地找到所有满足条件的子串。

步骤2：算法设计与步骤分解

解题思路

1. 变量初始化

   • 获取 inputString 的长度 inputLength，wordList 的单词数量 wordCount，每个单词的长度 wordLength，以及所有单词拼接后的总长度 totalWordsLength。
   • 如果 inputString 的长度小于 totalWordsLength，则没有可能的结果，直接返回空向量。

2. 词频统计

   • 使用哈希表 wordFrequencyMap 统计 wordList 中各个单词的出现次数，以便在后续判断子串中的单词是否符合要求。

3. 滑动窗口遍历

   • 对字符串 inputString 的所有可能的起点进行遍历（从 0 到 wordLength - 1），从不同起点来进行窗口滑动，确保覆盖所有可能的位置。
   • 对每一个可能的起点，使用左右指针 (leftPointer 和 rightPointer) 实现滑动窗口，窗口的长度为 wordLength 的整数倍。
   • 窗口逻辑：
     • 使用右指针 rightPointer 遍历字符串，每次获取当前窗口中的单词。
     • 如果当前单词在 wordList 中存在，则更新当前窗口的单词频率 currentWindowFrequencyMap。
     • 如果窗口中某个单词的频率超出了 wordFrequencyMap 中的值，则使用左指针 leftPointer 移动窗口，直到频率符合要求。
     • 当窗口内的单词数量等于 wordList 中的单词数量时，记录当前左指针位置为结果索引。
     • 如果遇到一个无效的单词（不在 wordList 中），则清空窗口的频率统计，并将左指针直接移动到下一个位置。

4. 复杂度分析

   • 时间复杂度：
     • 滑动窗口的起点有 wordLength 种可能，每次滑动时右指针从左到右遍历整个字符串，因此时间复杂度为 O(wordLength * (inputLength / wordLength))，即 O(inputLength)。
     • 在窗口滑动过程中，每次插入和查找操作的时间复杂度为 O(1)，因此整体时间复杂度为 O(inputLength)。
   • 空间复杂度：
     • 使用了两个哈希表来记录词频信息，空间复杂度为 O(wordCount)，其中 wordCount 是 wordList 的大小。

步骤3：c++代码

步骤4：算法优化与效率提升的启发

1. 滑动窗口的使用：

   • 这种滑动窗口加哈希表的方法可以有效减少重复计算，尤其是当窗口向右滑动时，不需要完全重新统计每个单词，只需要更新窗口内的变化。
   • 在大规模数据处理时，滑动窗口是一种非常有效的技术，用于在给定窗口内不断更新计算。

2. 哈希表的快速查找：

   • 利用哈希表存储词频，可以在 O(1) 的时间内查找单词的出现次数，这极大地提高了匹配的效率。
   • 通过词频统计，可以轻松处理包含重复单词的情况。

3. 优化潜力：

   • 如果 words 中有较多重复单词，可能可以进一步优化数据结构，例如使用自定义的计数器类来减少哈希表查找的开销。
   • 如果 words 中单词长度较长，可以考虑使用字符串哈希或其他方法来优化字符串匹配的效率。

步骤5：实际应用场景分析

实际应用示例：日志分析和关键字检测：

• 场景：
  • 在日志分析中，我们可能需要检测系统日志中的特定模式，确保某些关键字以某种顺序或组合出现，例如检测网络攻击模式、用户行为分析等。
• 实现方法：
  • 可以将系统日志作为字符串 s，而 words 则是需要检测的关键字列表。使用上述算法，我们可以快速找出哪些位置出现了所有关键字的组合，这对日志监控、入侵检测等非常有用。
  • 在实际中，这种方式可以被嵌入到自动化监控系统中，持续对实时日志进行分析，以便及时发现异常模式和潜在威胁。

通过上述步骤，我们不仅解决了一个算法问题，还展示了如何将这种算法应用到现实生活中，从而优化效率、提升生产力。在类似的应用中，处理大规模字符串匹配和检测，结合滑动窗口、哈希表等高效算法是一个有效的方案。