学做网站教程视频,南宁江南区网站制作价格,网站新年特效,懒设计官网KMP算法#xff08;Knuth-Morris-Pratt算法#xff09;是一种高效的字符串匹配算法#xff0c;用于在主文本字符串中快速查找模式字符串的出现位置。其核心思想是通过预处理模式字符串#xff0c;利用部分匹配信息#xff08;即“失败函数”或“next数组”#xff09;避免…KMP算法Knuth-Morris-Pratt算法是一种高效的字符串匹配算法用于在主文本字符串中快速查找模式字符串的出现位置。其核心思想是通过预处理模式字符串利用部分匹配信息即“失败函数”或“next数组”避免在匹配失败时回溯主串从而将时间复杂度优化到 O(nm)n是主串长度m是模式串长度远优于暴力匹配算法的 O(n×m)。 一核心原理 部分匹配表Prefix Table / Next数组 定义next[i] 表示模式串的子串 P[0...i] 的最长公共前后缀长度。作用当字符匹配失败时根据 next 数组决定模式串的回溯位置避免重复比较主串。 匹配过程 主串指针不回溯仅移动模式串指针 若当前字符匹配失败模式串指针回退到 next[j] 的位置继续匹配。 二Next数组的构建
最长前缀概念 最长前缀是说以第一个字符开始但是不包含最后一个字符。 最长后缀概念 最长后缀是说以最后一个字符开始但是不包含第一个字符。 next 数组定义在模式串中下标从0开始next[i] 表示模式串中以下标 i 处字符结尾的子串的最大相同前后缀的长度。在KMP算法中该值一方面表示模式串中1~i位置子串中的最长相同前后缀长度另一方面表示在该位置匹配失败时模式串回溯比较的下一个字符位置最长前缀末座标的下一个字符
步骤示例模式串 P ABABCABAB
索引子串最长公共前后缀next[i]0A无01AB无02ABA“A”13ABAB“AB”24ABABC无05ABABCA“A”16ABABCAB“AB”27ABABCABA“ABA”38ABABCABAB“ABAB”4
最终 next [0, 0, 1, 2, 0, 1, 2, 3, 4]。
构建代码Python
def build_next(pattern):next [0] * len(pattern)j 0 # 前缀末尾指针for i in range(1, len(pattern)): # 后缀末尾指针while j 0 and pattern[i] ! pattern[j]:j next[j-1] # 回退到前一个匹配位置if pattern[i] pattern[j]:j 1next[i] jreturn next# 示例模式串 ABABCABAB
print(build_next(ABABCABAB)) # 输出 [0, 0, 1, 2, 0, 1, 2, 3, 4]三匹配过程代码Python
def kmp_search(text, pattern):next build_next(pattern)j 0 # 模式串指针for i in range(len(text)): # 主串指针while j 0 and text[i] ! pattern[j]:j next[j-1] # 模式串回退if text[i] pattern[j]:j 1if j len(pattern):return i - j 1 # 返回匹配的起始位置return -1# 示例
text ABABABCABABABD
pattern ABABCABAB
print(kmp_search(text, pattern)) # 输出 2从索引2开始匹配多次出现的位置 def kmp_search(text, pattern):index [] next build_next(pattern)j 0 # 模式串指针for i in range(len(text)): # 主串指针while j 0 and text[i] ! pattern[j]:j next[j-1] # 模式串回退if text[i] pattern[j]:j 1if j len(pattern):#return i - j 1 # 返回匹配的起始位置index.append(i - j 1)j next[j-1]return index匹配失败时失败位置之前的主串i前和子串j前部分一定都是匹配的。且对于子串来说失败位置之前j前的任一部分属于子串模式串的这段子串子子串的后缀 重新匹配时我们重新匹配的开始一定是子串模式串的某部分前缀 要想移动子串模式串指针i 下次匹配位置到最大有效匹配位置那么这个位置一定是这段前缀后缀的部分
四关键点 时间复杂度 预处理模式串构建 next 数组O(m)匹配过程O(n)总体O(n m). 优势 避免主串指针回溯适合处理大文本流或实时数据。 应用场景 文本编辑器中的查找功能如CtrlF、代码解析、DNA序列匹配等。 无对比暴力匹配
暴力匹配每次失配后主串和模式串指针均回退重复比较已匹配的字符。主串A B A B A B C
模式A B A B C
暴力匹配需要回退主串指针比较多次。KMP主串指针不回溯仅调整模式串指针效率显著提升。 掌握KMP算法的核心在于理解部分匹配表的构建逻辑和失配时的回溯策略。
