python 149字符串匹配KMP算法
时间: 2024-01-02 19:22:41 浏览: 52
KMP算法是一种高效的字符串匹配算法,它利用了匹配失败后的信息,减少了模式串与主串的匹配次数,从而实现快速匹配。下面是Python实现字符串匹配的KMP算法的示例代码:
```python
def get_next(pattern):
next = [-1] * len(pattern)
i, j = 0, -1
while i < len(pattern) - 1:
if j == -1 or pattern[i] == pattern[j]:
i += 1
j += 1
next[i] = j
else:
j = next[j]
return next
def kmp_search(text, pattern):
next = get_next(pattern)
i, j = 0, 0
while i < len(text) and j < len(pattern):
if j == -1 or text[i] == pattern[j]:
i += 1
j += 1
else:
j = next[j]
if j == len(pattern):
return i - j
else:
return -1
text = "ABABABABCABABABABCABABABABC"
pattern = "ABABCABAB"
index = kmp_search(text, pattern)
print("Pattern found at index:", index) # 输出:Pattern found at index: 10
```
以上代码中,`get_next`函数用于计算模式串的next数组,`kmp_search`函数用于进行KMP算法的匹配操作。在示例中,我们在文本字符串`text`中查找模式串`pattern`,并返回匹配的起始位置。
相关推荐
![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)