m数据结构 day7 串（二）KMP模式匹配算法

科技前沿 • 2025-01-18 11:54 • 阅读 55

m数据结构 day7 串（二）KMP模式匹配算法文章目录 KMP 算法 KNP 算法的灵魂主串指针 i 不回溯模式串指针 j 的回溯量取决于 j 当前指向的字符之前的串模式串的子串的前后缀的相似度串的 next 数组简单 next i 的值减 1 就是模式串 j 从 1 到 i 1 的子串的最长公共前后缀的长度 KMP 的代码返回子串 T 的 next 数组难

大家好，我是讯享网，很高兴认识大家。

讯享网

文章目录

KMP算法
- KNP算法的灵魂：主串指针i不回溯，模式串指针j的回溯量取决于j当前指向的字符之前的串（模式串的子串）的前后缀的相似度
- 串的next数组：简单，next[i]的值减1 就是模式串j从1到i-1的子串的最长公共前后缀的长度
- KMP的代码
- - 返回子串T的next数组，难,时间复杂度O(m),m是子串长度
  - 用KMP进行模式匹配，返回模式串在主串中的位置，时间复杂度O(m+n)
- 和朴素遍历算法的对比：KMP在模式和主串之间存在许多“部分匹配”时优势明显
KMP算法的改进:改进next数组为nextval，减少j回溯时的多余判断
- nextval数组值推导
- - 推导公式
  - 原理
- 例子
- 计算nextval数组的函数代码