1355：字符串匹配问题(strs)

### 回答1：
题目描述：

给定一个字符串数组 strs 和一个字符串 str，找到 strs 中所有可以与 str 匹配的字符串，返回这些字符串的索引。

示例：

输入：strs = ["abc","def","efg","hij","klm"], str = "ef"
输出：[1,2]

解释：strs[1] 和 strs[2] 可以与 str 匹配。

思路：

遍历字符串数组，对于每个字符串，判断是否包含目标字符串，如果包含，则将该字符串的索引加入结果数组中。

代码实现：

class Solution:
def strStr(self, strs: List[str], str: str) -> List[int]:
res = []
for i in range(len(strs)):
if str in strs[i]:
res.append(i)
return res

### 回答2：
题目描述：

给定模式串 pat，文本串 txt，在文本串中寻找是否存在与模式串匹配的子串，如果存在，则返回该子串在文本串中的起始位置。如果不存在，则返回 -1。

解题思路：

1. 暴力匹配

最简单的思路就是暴力扫描，在文本串中从前往后扫描，将每一个字符都与模式串中的每一个字符相比较。需要注意的是，扫描时要考虑到匹配的长度不超过文本串的长度。

时间复杂度：O(m*n)，其中 m 是模式串的长度，n 是文本串的长度。

2. KMP 算法

KMP 算法是一种字符串匹配算法，其核心思想是利用已知信息避免在匹配过程中重复比较。具体来讲，就是对于模式串中每一个字符，预处理出一个关于该字符的“部分匹配表”，即在模式串中该字符之前的字符串的最长相同前缀和后缀的长度。在匹配时，如果匹配过程中出现了不匹配的字符，就利用该字符对应的“部分匹配表”信息，将模式串中的指针向右移动一定的位数，从而实现跳过已经匹配过的位置重新匹配。

时间复杂度：O(m+n)，其中 m 是模式串的长度，n 是文本串的长度。

3. Boyer-Moore 算法

Boyer-Moore 算法也是一种字符串匹配算法。它的核心思想是从模式串的末尾开始匹配，每次匹配失败时，将模式串中的指针向右移动一定的位数并继续匹配。Boyce-Moore 算法的优点是约定每次跳过的字符都和模式串无关，从而提高匹配过程中的效率和减少比较次数。

时间复杂度：O(mn)，其中 m 是模式串的长度，n 是文本串的长度。

4. Rabin-Karp 算法

Rabin-Karp 算法是一种基于哈希表的字符串匹配算法。它的核心思想是将模式串和文本串对应的字符串看作一个整体，计算它们的哈希值后进行比较，从而判断它们是否相等。在计算哈希值时，可以利用哈希值的加法性质和减法性质，减小哈希值的计算量。如果哈希值相等，则进行字符比较，以确认是否真的匹配成功。

时间复杂度：O(m+n)，其中 m 是模式串的长度，n 是文本串的长度。

总结：

以上四种算法分别是暴力匹配、KMP 算法、Boyer-Moore 算法和Rabin-Karp 算法。不同的算法可以有不同的时间复杂度和空间复杂度，从而在不同的场景中具有不同的应用价值。所以，在实际的应用场景中，可以根据具体的需求选择合适的算法进行实现。

### 回答3：
题目描述

给定一个字符串 s 和一个字符串数组 strs，找到 strs 中所有是 s 的子串的字符串，返回这些字符串的索引。s 不重复，同时 strs 中的所有字符串都是不重复的。

示例:

输入: s = "barfoothefoobarman", strs = ["foo","bar"]
输出: [0,9]
解释: 输出索引为0的"bar"对应匹配串是"bar", 索引为9的"foo"对应匹配串是"foo"。

解题思路

这道题需要使用到字符串匹配，可以使用暴力匹配的思想，在 s 中每次尝试匹配 strs 中的所有字符串。但是由于 s 和 strs 都很长，这样的时间复杂度比较高。

因此，我们可以使用字典树的思路，将 strs 中的所有字符串都加入字典树中，然后在 s 中依次匹配所有字符串。具体步骤如下：

1. 将 strs 中所有字符串加入字典树中。

2. 对于字符串 s，从第一个字符开始，在字典树中查找所有可能的匹配字符串，并记录其位置。

3. 继续向后查找，重复 2 的操作。

4. 最终，返回所有匹配的字符串的位置。

代码实现

以下是 Python3 代码实现：