【数据结构】朴素模式匹配 & KMP算法

**数据结构之朴素模式匹配与KMP算法**

在计算机科学中，模式匹配是指在一个字符串中找到另一个子串的过程。这种问题经常出现在文本编辑、编译器、数据库等领域。在本文中，我们将介绍两种常见的模式匹配算法：朴素模式匹配和KMP（Knuth-Morris-Pratt）算法。

**1.朴素模式匹配**

朴素模式匹配是最简单的一种模式匹配算法。其基本思想是将模式串与主串逐一比较，直到找到一个完全匹配的子串为止。

###朴素模式匹配的步骤：

1. 将模式串和主串都转换成小写或大写。
2. 从主串的第一个字符开始，与模式串的第一个字符进行比较，如果不相等，则移动到下一个位置，直到找到一个完全匹配的子串为止。

###朴素模式匹配的代码示例：

def naive_pattern_matching(pattern, text):
 # 将模式串和主串都转换成小写或大写。
 pattern = pattern.lower()
 text = text.lower()

 # 从主串的第一个字符开始，与模式串的第一个字符进行比较。
 for i in range(len(text) - len(pattern) +1):
 match = True for j in range(len(pattern)):
 if text[i + j] != pattern[j]:
 match = False break # 如果找到一个完全匹配的子串，则返回该位置。
 if match:
 return i # 如果没有找到任何匹配的子串，则返回-1。
 return -1# 测试函数text = "Hello, world!"
pattern = "world"
index = naive_pattern_matching(pattern, text)
if index != -1:
 print(f"模式'{pattern}'在主串'{text}'中找到，位置为{index}")
else:
 print(f"模式'{pattern}'在主串'{text}'中未找到")

def compute_prefix_suffix_array(pattern):
 # 预处理模式串，计算出模式串中每个子串的最大前缀后缀长度。
 prefix_suffix_array = [0] * len(pattern)
 j =0 for i in range(1, len(pattern)):
 while j >0 and pattern[i] != pattern[j]:
 j = prefix_suffix_array[j -1]
 if pattern[i] == pattern[j]:
 j +=1 prefix_suffix_array[i] = j return prefix_suffix_arraydef kmp_pattern_matching(pattern, text):
 # 将模式串和主串都转换成小写或大写。
 pattern = pattern.lower()
 text = text.lower()

 # 预处理模式串，计算出模式串中每个子串的最大前缀后缀长度。
 prefix_suffix_array = compute_prefix_suffix_array(pattern)

 # 从主串的第一个字符开始，与模式串的第一个字符进行比较。
 for i in range(len(text) - len(pattern) +1):
 j =0 for k in range(len(pattern)):
 if text[i + k] != pattern[k]:
 break j +=1 # 如果找到一个完全匹配的子串，则返回该位置。
 if j == len(pattern):
 return i # 如果没有找到任何匹配的子串，则返回-1。
 return -1# 测试函数text = "Hello, world!"
pattern = "world"
index = kmp_pattern_matching(pattern, text)
if index != -1:
 print(f"模式'{pattern}'在主串'{text}'中找到，位置为{index}")
else:
 print(f"模式'{pattern}'在主串'{text}'中未找到")