kmp 算法
panyf
·
·
个人记录
kmp 算法用于在线性时间内求字符串的前缀最长 border，或求解字符串匹配问题。
定义字符串 s 的 border 为字符串 t，满足 t 是 s 的前缀也是 s 的后缀，且 t 不是 s 本身。
考虑现在给定两个字符串 s,t，求 t 在 s 出现的所有位置。
以下默认字符串下标从 1 开始。
记 pre_i 为 t 的长度为 i 的前缀。
首先预处理数组 p，p_i 表示 pre_i 的最长 border 的长度。
这里数组 p 就是所谓的 next 数组。
初始化 p_1=0。
考虑现在求 p_i，令 j=p_{i-1}。
1.若 t_i=t_{j+1}，则 p_i=j+1。
2.否则若 j=0，则 p_i=0。
3.否则，考虑一个 x 满足 x<j，并且 pre_{x+1} 是 pre_i 的 border。
那么一定有 pre_x 是 pre_{i-1} 的 border。
又因为 x<j，且 pre_j 是 pre_{i-1} 的 border，所以 pre_x 是 pre_j 的 border。
所以满足条件的最大的 x 就是 p_j。
所以可以 j\leftarrow p_j，然后返回第 1 步。
考虑这样做的时间复杂度，显然 j 每次最多 +1，所以 j 减少的次数也不超过 |t| 次，所以复杂度为 O(|t|)。
再考虑如何利用 p 数组求 t 在 s 中出现的所有位置。
考虑从前到后依次加入 s 的字符。
定义一个变量 j，表示最大的 x 满足当前已经加入的 s 的部分的长度为 x 的后缀和 pre_x 相同。
初始化 j=0。
考虑加入 s_i，若 s_i=t_{j+1}，则 j\leftarrow j+1。
若 j=|t|，则 s 的长度为 i 的前缀的长度为 j 的后缀和 t 相同，找到了一个 t 在 s 中出现的位置，为 i-|t|+1。
若 s_i\neq t_{j+1}，则 j\leftarrow j+1，重复此步骤直到 s_i=t_{j+1} 或 j=0。
容易发现这部分的做法和预处理 p 数组时类似，所以正确性不再赘述，复杂度 O(|s|)。
总复杂度 O(|s|+|t|)。
模板题：P3375 【模板】KMP字符串匹配 提交记录
习题：
P3435 [POI2006]OKR-Periods of Words
P2375 [NOI2014] 动物园
P4824 [USACO15FEB]Censoring S
CF1017E The Supersonic Rocket
P3193 [HNOI2008]GT考试
P3426 [POI2005]SZA-Template
P5829 【模板】失配树