难度: Medium
给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。
示例：
输入： big = "mississippi" smalls = ["is","ppi","hi","sis","i","ssippi"] 输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
提示：
0 <= len(big) <= 10000 <= len(smalls[i]) <= 1000smalls的总字符数不会超过 100000。smalls中没有重复字符串。运行时间: 106 ms
内存: 35.2 MB
class Solution:
def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
if len(smalls) < 1:
return []
if len(smalls) == 1:
return [[]]
res = []
for i in smalls:
temp = []
if i in big:
for j in range(len(big)-len(i)+1):
if big[j:j+len(i)] == i:
temp.append(j)
res.append(temp)
return res
此题解采用的是暴力匹配的方式来找出small中的字符串在big字符串中的所有出现位置。首先，它检查smalls数组是否为空或只含有一个元素。接着，它创建一个结果列表res来存储每个smalls中字符串的匹配位置。对于smalls中的每个字符串，它首先检查该字符串是否存在于big中。如果存在，它则遍历big字符串，通过比较子字符串big[j:j+len(i)]与smalls中的字符串i，来确定所有匹配的起始位置，并将它们添加到一个临时列表temp中。最后，将temp添加到结果列表res中。
时间复杂度: O(S*len(big))
空间复杂度: O(S + len(big))
class Solution:
def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
if len(smalls) < 1: # 检查smalls是否为空
return []
if len(smalls) == 1: # 检查smalls是否只有一个元素
return [[]]
res = [] # 结果列表
for i in smalls:
temp = [] # 临时列表，存储当前small字符串的所有匹配位置
if i in big: # 检查当前字符串是否存在于big中
for j in range(len(big)-len(i)+1): # 遍历big以查找所有可能的起始位置
if big[j:j+len(i)] == i: # 如果子字符串与small字符串匹配
temp.append(j) # 将匹配的起始位置添加到temp中
res.append(temp) # 将当前small字符串的所有匹配位置添加到结果列表中
return res
选择使用暴力匹配方法可能是因为问题的特定上下文或简化实现的考虑。暴力匹配方法代码简单，易于理解和实现，适用于问题规模较小或对性能要求不是非常严格的情况。相比之下，如KMP、Rabin-Karp和Boyer-Moore等算法虽然在最坏情况下提供更好的性能，但它们的实现更复杂，调试和维护更困难。如果big和smalls的大小不是非常大，或者是教学示例的一部分，使用暴力匹配方法可能就足够了。
在实现中进行 `if i in big` 检查的目的是提前过滤掉那些根本不可能在big中找到的small字符串，从而可能减少不必要的遍历。这个检查可以快速确定是否有必要进行后续的详细匹配过程。如果一个small字符串不在big中，那么可以立即跳过对该字符串的进一步搜索，节省计算资源。虽然这看似增加了一次全文扫描的开销，但它实际上能在某些情况下减少整体的计算量，尤其是当smalls中包含多个不可能匹配的字符串时。
确实，使用后缀数组或后缀树可以显著优化大规模字符串搜索问题的效率。后缀树和后缀数组允许在预处理阶段花费一定的时间来构建索引，之后可以非常快速地处理多个查询。这种数据结构特别适用于需要频繁搜索多个小字符串（smalls）在一个大字符串（big）中的位置的情况。通过这样的预处理，搜索每个small字符串的时间复杂度可以降低到接近线性，这对于大数据量的应用是非常有益的。因此，对于大规模数据或高性能需求的应用场景，采用这些高效的数据结构是更优的选择。