本文目录
1 算法原理
KMP（Knuth-Morris-Pratt）算法是一种用于高效字符串匹配的算法。它通过预处理模式字符串，构建一个部分匹配表（前缀函数），以避免重复比较，从而提高匹配效率。KMP 算法通过利用部分匹配表来记录模式字符串的前缀信息。当在文本中进行匹配时，借助这个表快速跳过不必要的字符。
1.1 部分匹配表
部分匹配表（也称为前缀函数）在 KMP 算法中起着关键作用，通过记录模式字符串中相同前后缀的长度，帮助在匹配失败时快速跳过不必要的比较。具体作用
- 避免重复比较：
- 当模式中的字符与文本不匹配时，部分匹配表指示下一个可能匹配的位置。
- 这避免了重新从头开始匹配，节省了时间。
- 快速移动模式：
- 当发生不匹配时，通过前缀函数确定模式中可以直接跳过多少字符，从而加速匹配过程。
核心概念
- 相同前后缀长度：