子串在父串出现的所有位置
时间: 2024-02-05 13:12:30 浏览: 39
要找到一个字符串在另一个字符串中出现的所有位置,可以使用字符串匹配算法。
一种常见的字符串匹配算法是 KMP 算法。该算法的基本思想是,当发现不匹配时,不需要每次都从头开始匹配,而是利用已经匹配的信息,尽可能地减少比较次数。
下面是一个使用 KMP 算法找到子串在父串出现的所有位置的示例代码:
```python
def kmp(pattern, text):
m = len(pattern)
n = len(text)
# 构建前缀表
prefix = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[j] != pattern[i]:
j = prefix[j-1]
if pattern[j] == pattern[i]:
j += 1
prefix[i] = j
# 在文本中查找模式
j = 0
matches = []
for i in range(n):
while j > 0 and pattern[j] != text[i]:
j = prefix[j-1]
if pattern[j] == text[i]:
j += 1
if j == m:
matches.append(i-m+1)
j = prefix[j-1]
return matches
# 示例
text = "abababab"
pattern = "aba"
matches = kmp(pattern, text)
print(matches) # 输出 [0, 2, 4]
```
在上面的示例中,`kmp` 函数接收两个参数:`pattern` 表示要查找的子串,`text` 表示父串。函数首先构建模式串的前缀表,然后在文本中查找模式串,将所有匹配的位置存储在 `matches` 列表中,并返回该列表。
这个算法的时间复杂度是 $O(m+n)$,其中 $m$ 是模式串的长度,$n$ 是文本串的长度。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)