knuth-morris-pratt算法
时间: 2023-04-27 08:01:22 浏览: 70
Knuth-Morris-Pratt算法,简称KMP算法,是一种字符串匹配算法。它的主要思想是利用已知信息来避免无用的比较,从而提高匹配效率。KMP算法的时间复杂度为O(m+n),其中m和n分别为模式串和文本串的长度。KMP算法的实现过程中,需要先预处理出模式串的next数组,然后利用next数组进行匹配。KMP算法在实际应用中具有广泛的应用,例如字符串匹配、图像处理、自然语言处理等领域。
相关问题
串匹配 Naïve算法 Rabin-Karp算法 Knuth-Morris-Pratt算法
串匹配是指在一个文本串中查找另一个模式串的过程。常用的串匹配算法有Naïve算法、Rabin-Karp算法和Knuth-Morris-Pratt算法。
1. Naïve算法
Naïve算法是最简单的串匹配算法,也称为暴力匹配算法。它的思路是从文本串的第一个字符开始,依次比较文本串中的每个字符是否与模式串中的字符相等。若不相等,则继续向后比较;若相等,则比较下一个字符,直到找到完全匹配的子串或文本串被匹配完为止。
Naïve算法的时间复杂度是O(mn),其中m和n分别是模式串和文本串的长度。当模式串和文本串长度相等时,最坏情况下时间复杂度达到O(n^2)。
2. Rabin-Karp算法
Rabin-Karp算法是一种基于哈希值的串匹配算法。它的思路是先将模式串和文本串都转换为哈希值,然后比较它们的哈希值是否相等。如果哈希值相等,则再逐个比较模式串和文本串中的字符是否相等。这种方法可以有效地减少比较次数,提高匹配效率。
Rabin-Karp算法的时间复杂度是O(m+n),其中m和n分别是模式串和文本串的长度。但是,由于哈希函数的不完全性和哈希冲突的存在,Rabin-Karp算法在某些情况下可能会出现误判。
3. Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法是一种基于前缀函数的串匹配算法。它的思路是先计算出模式串的前缀函数,然后利用前缀函数的信息来跳过已经匹配过的部分,减少比较次数。
具体来说,KMP算法在匹配过程中维护一个指针i和一个指针j,其中i指向文本串中当前匹配的位置,j指向模式串中当前匹配的位置。如果当前字符匹配成功,则i和j同时向后移动一位;如果匹配失败,则通过前缀函数计算出j需要跳转到的位置,使得前j-1个字符与文本串中的对应字符已经匹配成功,然后将j指向这个位置,i不变,继续比较下一个字符。
KMP算法的时间复杂度是O(m+n),其中m和n分别是模式串和文本串的长度。由于利用了前缀函数的信息,KMP算法可以在最坏情况下达到O(n)的时间复杂度,比Naïve算法和Rabin-Karp算法更加高效。
串的模式匹配算法--BF算法/KMP算法
BF算法和KMP算法都是串的模式匹配算法,但是它们的时间复杂度不同。BF算法的时间复杂度为O(m*n),其中m和n分别为主串和模式串的长度。而KMP算法的时间复杂度为O(m+n)。因此,当模式串较长时,KMP算法的效率更高。
下面是BF算法和KMP算法的介绍和演示:
1. BF算法(暴力匹配算法)
BF算法是一种朴素的模式匹配算法,它的思想是从主串的第一个字符开始,依次和模式串的每个字符进行比较,如果匹配成功,则继续比较下一个字符,否则从主串的下一个字符开始重新匹配。BF算法的时间复杂度为O(m*n)。
下面是BF算法的Python代码演示:
```python
def BF(main_str, pattern_str):
m = len(main_str)
n = len(pattern_str)
for i in range(m-n+1):
j = 0
while j < n and main_str[i+j] == pattern_str[j]:
j += 1
if j == n:
return i
return -1
# 测试
main_str = 'ababcabcacbab'
pattern_str = 'abcac'
print(BF(main_str, pattern_str)) # 输出:6
```
2. KMP算法(Knuth-Morris-Pratt算法)
KMP算法是一种改进的模式匹配算法,它的核心思想是利用已经匹配过的信息,尽量减少模式串与主串的匹配次数。具体来说,KMP算法通过预处理模式串,得到一个next数组,用于指导匹配过程中的跳转。KMP算法的时间复杂度为O(m+n)。
下面是KMP算法的Python代码演示:
```python
def KMP(main_str, pattern_str):
m = len(main_str)
n = len(pattern_str)
next = getNext(pattern_str)
i = 0
j = 0
while i < m and j < n:
if j == -1 or main_str[i] == pattern_str[j]:
i += 1
j += 1
else:
j = next[j]
if j == n:
return i - j
else:
return -1
def getNext(pattern_str):
n = len(pattern_str)
next = [-1] * n
i = 0
j = -1
while i < n-1:
if j == -1 or pattern_str[i] == pattern_str[j]:
i += 1
j += 1
next[i] = j
else:
j = next[j]
return next
# 测试
main_str = 'ababcabcacbab'
pattern_str = 'abcac'
print(KMP(main_str, pattern_str)) # 输出:6
```