KMP 字符串匹配算法 Python 实现

本代码实现了经典的 KMP 字符串匹配算法，该算法能够在线性时间复杂度内高效地找到模式串在文本串中出现的所有位置。

def kmp_search(text, pattern):
  """
  使用 KMP 算法在文本串中查找模式串的所有出现位置。

  Args:
    text: 文本串。
    pattern: 模式串。

  Returns:
    一个列表，包含模式串在文本串中所有出现位置的起始索引。
  """

  n = len(text)
  m = len(pattern)
  if m == 0:
    return [0]

  # 计算模式串的 next 数组
  next = [0] * (m + 1)
  j = 0
  for i in range(1, m):
    while j > 0 and pattern[i] != pattern[j]:
      j = next[j]
    if pattern[i] == pattern[j]:
      j += 1
    next[i + 1] = j

  # 在文本串中查找模式串
  j = 0
  occurrences = []
  for i in range(n):
    while j > 0 and text[i] != pattern[j]:
      j = next[j]
    if text[i] == pattern[j]:
      j += 1
    if j == m:
      occurrences.append(i - m + 1)
      j = next[j]

  return occurrences

使用方法:

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

occurrences = kmp_search(text, pattern)

print(f"模式串在文本串中的出现位置：{occurrences}")

输出:

模式串在文本串中的出现位置：[10]