KMP算法用于实现字符串匹配问题。例如查找某个字符串是否是s的子串。

我们先来看一道题

一.力扣28.找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

        对于这种题目,我们首先想到的就是使用两个for循环,依次找每一种可能,看看能不能找到匹配的字符串

1.传统for循环

思路:

• 将主串 T（长度为 n）与模式串 P（长度为 m）依次对齐比较。

• 对齐位置 i 从 0 到 n-m，每次比较 T[i..i+m-1] 与 P[0..m-1]。

• 若某个字符不匹配，则模式串向右移动 1 位，重新从头比较。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.length();
        int m = needle.length();
        
        // needle 为空字符串的情况
        if (m == 0) return 0;
        
        // 主循环，尝试所有可能的起始位置
        for (int i = 0; i <= n - m; i++) {
            int j;
            // 检查当前位置是否匹配
            for (j = 0; j < m; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            // 如果完全匹配
            if (j == m) {
                return i;
            }
        }
        //没找到就返回-1
        return -1;
    }
};

        这种传统解法的时间复杂度是O(n*m),n和m分别是两个字符串的长度,对于最坏的情况,需要搜索n*m次.

        那我们可不可以进行优化呢,让搜索的次数减少,以此来降低时间复杂度,当然可以,这就是KMP算法的思想

2.KMP算法

①什么是KMP算法

        KMP算法用于实现字符串匹配问题。例如查找某个字符串是否是s的子串。普通方法是从s字符串的开头开始一次比较。时间复杂度O(n*m)。KMP该是该方法的优化方法。

        KMP算法的核心思想,就是每次如果字符串没有匹配成功,不是从头开始重新查找,而是从一个特定的合理位置开始继续查找,减少了查找次数

        那我们应该如何去找到这个特定的合理位置呢,这就是KMP算法的关键,引入一个前缀表的概念

②前缀表

        前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

        前缀是指不包含最后一个字符，以第一个字符开头的连续子串。

        后缀是指不包含第一个字符，以最后一个字符结尾的连续子串

        前缀表要求的就是相同前后缀的长度

        字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。

 ③next数组

        KMP算法就是把子串中的每个位置对应的最长相同前后缀长度,记录在next数组中,一旦匹配失败,就从当前已匹配位置的最长前缀长度继续进行匹配(next[i-1])

④代码实现

1)构建next数组

构建next数组的过程,实际上就是子串自己进行KMP算法的过程

void getNext(vector<int>& next, string& needle) {
    //初始化最大前后缀长度
    int j = 0;
    //第一个位置的字母相同前后缀长度是0
    next[0] = 0;
    
    //开始循环查找
    for (int i = 1;i < needle.size();i++) {
        //如果不同,就从已经匹配的最大位置开始重新匹配,直到匹配成功
        while (j > 0 && needle[i] != needle[j]) {
            j = next[j - 1];
        }
        
        //如果相同,就将前后缀长度+1
        if (needle[i] == needle[j]) {
            j++;
        }

        //给当前位置赋值
        next[i] = j;
    }
}

2)查找第一个匹配项位置

int KMP(string s, string s1) {
    //字符串为空或者子串长度更大都是错误的
    if (s1.size() == 0 || s.size() == 0 || s.size() < s1.size()) {
        return -1;
    }
    
    //初始化next数组
    vector<int>next(s1.size(),0);
    //调用方法得到next数组
    getNext(next, s1);

    //开始查找
    int j = 0;
    for (int i = 0;i < s.size();i++) {
        //和构建next数组一样,如果不匹配,就从已匹配的最长位置重新开始
        while (j > 0 && s[i] != s1[j]) {
            j = next[j - 1];
        }
        
        //如果相同,就将已匹配长度+1
        if (s[i] == s1[j]) {
            j++;
        }

        //终止条件是已匹配长度和子串长度相等,说明全部匹配
        if (j == s1.size()) {
            return i - s1.size() + 1;
        }
    }
    return -1;
}

3)举一反三

如果题目要求查找所有匹配项,就将KMP函数中查找成功的部分改为

vec.push_back(i - s1.size() + 1);//存储结果
j=next[j-1];//继续查找

4)效率分析

        对于传统的双重for循环的O(n*m)的时间复杂度,KMP算法可以将其降至O(n+m),大大优化了传统方法

        在最坏的情况下,如子串是ac,父串是aaa...ac时效果更加明显

3.方法比较

算法	时间复杂度	空间复杂度	优点	缺点
暴力匹配	O(n × m)	O(1)	实现简单，代码短	最坏情况下效率低
KMP	O(n + m)	O(m)	效率高，适合长字符串	实现复杂，需要额外空间

二.KMP算法小结

• 核心是 最长公共前后缀（LPS），用于跳过已匹配部分。

• next 数组是预处理的移位/变形。

• 匹配时主串指针不回退，模式串指针根据 next 回退。

• 适合在流式文本中匹配，因为不需要全文存储。

KMP算法属于比较抽象难想的算法,建议画一画,模拟一下整个过程来帮助理解