KMP 算法笔记

· · 个人记录

综述

KMP 算法是一个在 O(n+m) 的时间复杂度中求出模式串在文本串中的出现位置的算法.

算法简述

这里记文本串为 S_1，模式串为 S_2.

KMP 算法的核心在于失配时快速恢复，其恢复位置需要在开始时预处理，这里记为 \{nxt\}.

而 \{nxt\} 是对模式串的预处理得来的，对于 nxt_i 其所标记的为 S_{2,[1,i-1]} 最大的相同前后缀（即令子串的前缀和后缀相等的最长长度），\{nxt\} 的处理采用自匹配的方式得来，算法简述如下.

对于枚举到模式串 S_2 的第 i 位，即 S_{2,i} 时，记上一次自匹配成功在第 j 位，则有：

  2. 若 S_{2,i} = S_{2,j+1} 则 j \to j+1.

  3. 将 nxt_i \to j.