【代码随想录day9】KMP算法-找出字符串中第一个匹配项的下标

**代码随想录 Day9: KMP 算法**

在前面的几篇文章中，我们讨论了关于字符串匹配算法的基本概念，如 Brute Force、Rabin-Karp 等。然而，这些算法都有一个共同的问题：它们的时间复杂度都是 O(n*m)，其中 n 是主串的长度，m 是模式串的长度。这意味着当 n 和 m 很大时，这些算法会非常慢。

在本篇文章中，我们将讨论一种更高效的字符串匹配算法：KMP 算法。KMP 算法是由 Donald Knuth、James H. Morris Jr. 和 Vaughan Pratt 在1977 年提出的一种算法，它可以在 O(n+m) 的时间复杂度下找到主串中第一个匹配项的下标。

**什么是 KMP 算法？**

KMP 算法是一种预处理技术。它首先计算出模式串中所有可能的前缀和后缀的最大长度，这个长度就是我们要找的匹配项的长度。然后，它使用这个信息来跳过主串中的某些字符，从而减少匹配过程的时间复杂度。

**KMP 算法的步骤**

1. **预处理**:计算模式串中所有可能的前缀和后缀的最大长度，这个长度就是我们要找的匹配项的长度。
2. **主串扫描**:从主串的第一个字符开始，依次与模式串中的每个字符进行比较。如果匹配，则继续下一步。否则，从主串中跳过一些字符，然后再与模式串中的下一个字符进行比较。

**KMP 算法的实现**

def compute_prefix_function(pattern):
 """
 Compute the prefix function for KMP algorithm.
 Args:
 pattern (str): The pattern string.
 Returns:
 list: A list of integers representing the prefix function values.
 """
 m = len(pattern)
 pi = [0] * m j =0 for i in range(1, m):
 while j >0 and pattern[i] != pattern[j]:
 j = pi[j -1]
 if pattern[i] == pattern[j]:
 j +=1 pi[i] = j return pidef kmp_search(main_string, pattern):
 """
 Search for the first occurrence of the pattern in the main string using KMP algorithm.
 Args:
 main_string (str): The main string.
 pattern (str): The pattern string.
 Returns:
 int: The index of the first occurrence of the pattern if found, -1 otherwise.
 """
 pi = compute_prefix_function(pattern)
 m = len(pattern)
 n = len(main_string)
 j =0 for i in range(n):
 while j >0 and main_string[i] != pattern[j]:
 j = pi[j -1]
 if main_string[i] == pattern[j]:
 j +=1 if j == m:
 return i - m +1 return -1# Example usagemain_string = "banana"
pattern = "ana"
index = kmp_search(main_string, pattern)
print("The first occurrence of '{}' is at index {}".format(pattern, index))

在这个例子中，我们首先计算出模式串 "ana" 中所有可能的前缀和后缀的最大长度，这个长度就是我们要找的匹配项的长度。然后，我们使用 KMP 算法从主串 "banana" 的第一个字符开始，依次与模式串中的每个字符进行比较。如果匹配，则继续下一步。否则，从主串中跳过一些字符，然后再与模式串中的下一个字符进行比较。

最终结果是找到主串中第一个匹配项的下标，并打印出这个下标。

**总结**

KMP 算法是一种高效的字符串匹配算法，它可以在 O(n+m) 的时间复杂度下找到主串中第一个匹配项的下标。它通过预处理技术计算出模式串中所有可能的前缀和后缀的最大长度，然后使用这个信息来跳过主串中的某些字符，从而减少匹配过程的时间复杂度。

在本篇文章中，我们讨论了 KMP 算法的基本概念、步骤和实现。我们还提供了一个例子，展示了如何使用 KMP 算法找到主串中第一个匹配项的下标。