KMP算法

发布日期: 2021-05-07

阅读次数:

KMP 算法是一个快速查找匹配串的算法，它的作用其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。
上述的朴素解法，不考虑剪枝的话复杂度是 O(m * n)的，而 KMP 算法的复杂度为 O(m + n)。
KMP 之所以能够在 O(m + n)复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。

先记下模板，其他的后面再补吧φ(*￣0￣)

代码模板

/*
题目描述：
给你两个字符串 haystack 和 needle,请你在 haystack 字符串中找出 
needle字符串出现的第一个位置(下标从 0 开始).如果不存在,则返回-1。
*/
class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        if(m == 0) return 0;
        //设置哨兵,使其下标从 1 开始
        s.insert(s.begin(),' ');
        p.insert(p.begin(),' ');
        vector<int> next(m + 1);
        //预处理next数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        for(int i = 2, j = 0; i <= m; i++){
            // 匹配不成功的话，j = next(j)
            while(j and p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if(p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }
        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for(int i = 1, j = 0; i <= n; i++){
            // 匹配不成功 j = next(j)
            while(j and s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if(s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if(j == m) return i - m;
        }
        return -1;
    }
};