KMP算法笔记

共计 685 个字符，预计需要花费 2 分钟才能阅读完成。

提醒：本文最后更新于2025-03-07 17:21，文中所关联的信息可能已发生改变，请知悉！

介绍

$O(n)$时间复杂度匹配目标字符串的算法。

关于前缀函数

我觉得在KMP之前先讲一下前缀函数会更好一些，所谓前缀函数就是指当前字符串$s$的前$i$个字符组成的子串中前缀和后缀相同的字串的最大长度。举例来说：

$s = abcab$，那么前缀函数$f[5] = 2$，相同的子串为$ab$(我这里下标从$1$开始)。

前缀函数在KMP中的应用

我们观察一个这样的字符串$abcabd$，假如它在与母串匹配的过程中在最后一个字符$d$匹配失败了，按照朴素算法我们会重头开始，但是通过观察可以看出直接让当前母串的字符和第3个字符$c$匹配时更为合适的，因为我们发现在前5个字符当中存在相同的前缀和后缀子串，这实际上是可以重复利用的，而这个新的回溯位置我们也正好能够通过前缀函数得到。

初始化next数组

int ne[N] ;
void init(){
    for(int i = 2 ; j = 0; i < s.size() ; ++i){
        while( j && s[i] != s[j+1]) j = ne[j] ;
        if(s[i] == s[j+1]) ++ j ;
        ne[i] = j ;
    }
}

匹配字符串

for(int i = 0, j = 0 ; i < t.size() ; ++ i){
    while( j && t[i] != s[j+1]) j = ne[j] ;
    if(t[i] == s[j+1]) j ++ ;
    if(j == s.size()-1){
        cout << i - s.size() + 2 << " ";
        j = ne[j] ;
    }
 }

时间复杂度为什么是$O(n)$

我们可以发现j的增加只会来自if(t[i] == s[j+1]) j ++ ;这一步，(j)的最大值就是母串长度，假设$while$每次循环只会让$j$减少1，那么总共也只会减少母串长度次，所以总的时间复杂度就是$O(n)$。