100种算法【Python版】第15篇——KMP算法

1 算法原理

KMP（Knuth-Morris-Pratt）算法是一种用于高效字符串匹配的算法。它通过预处理模式字符串，构建一个部分匹配表（前缀函数），以避免重复比较，从而提高匹配效率。KMP 算法通过利用部分匹配表来记录模式字符串的前缀信息。当在文本中进行匹配时，借助这个表快速跳过不必要的字符。

1.1 部分匹配表

部分匹配表（也称为前缀函数）在 KMP 算法中起着关键作用，通过记录模式字符串中相同前后缀的长度，帮助在匹配失败时快速跳过不必要的比较。具体作用

• 避免重复比较：
  • 当模式中的字符与文本不匹配时，部分匹配表指示下一个可能匹配的位置。
  • 这避免了重新从头开始匹配，节省了时间。
• 快速移动模式：
  • 当发生不匹配时，通过前缀函数确定模式中可以直接跳过多少字符，从而加速匹配过程。

核心概念

• 相同前后缀长度：