自己对kmp算法的理解，借由 28. 实现 strStr() 为例

?做题思路 or 感想 ：

就借由这道题来理解一下kmp算法吧

  1. kmp算法的操作过程我觉得有句话很合适 ：KMP 算法永不回退 目标字符串 的指针 i，不走回头路（不会重复扫描 目标字符串），而是借助 next 数组中储存的信息把 模板字符串 移到正确的位置继续匹配

  2. kmp算法的重要点是计算next数组

    • i的含义是指向后缀末尾位置的下标，j的含义是指向前缀末尾位置的下标和最大前后缀和！！！

    • next[i]的定义是i（包括i）之前的最长前后缀之和

    • 对于for循环中为什么i要从1开始，因为i是后缀末尾，0是初始化的前缀末尾，如果要比较前后缀，则必须要是初始前缀末尾的正好后一位，这样子前后缀才能开始比较！

    • 当前后缀所表示的字符不相等，则

      while (j > 0 && s[j] != s[i]) {
	j = next[j - 1];
}

      上面是因为要找到一个和s[i]匹配的字符，或者直接降到第一个的 j = 0，所以要用while来控制

    • 当前后缀所表示的字符相等时，则

      if (s[i] == s[j]) {
	j++;	//这里我理解是因为j的含义是最长前后缀之和，而现在前后缀匹配了，所以前后缀之和长度要+1
}

    • 最后的最后，无论匹配或不匹配，都要给next[i]赋值，即是next[i] = j

  3. 最后是利用next数组来进行对目标字符串的匹配，这里carl哥没有详细讲，我就写点我自己的理解，有误是有误，但好歹是写给自己看的嘛，以后还可以改哈哈

    • 在匹配时，i的含义是目标字符串的匹配位置，j的含义是模板字符串的匹配位置（我可太容易在含义概念上搞混了）

    • 首先是匹配时的for (int i = 0; i < 目标字符串大小; i++)和next数组构建时有不同，因为这里比较的是两个串，所以要从一开始的下标0匹配，而构建next数组时是对一个串的前后缀匹配，所以构建next数组时i是要从1开始初始化

    • 然后由

      while (j > 0 && aim[i] != needle[j]) {	//用的是while
	j = next[j - 1];	//注意这里是看前一位的next数组来进行回退操作
}

      来确定模板字符串的匹配位置

    • 如果aim[i] == needle[j]则匹配成功，则有j++使得匹配位置往前进一步

回到一开始的这道题，其实就是把上面的操作全部抄一遍就好了，二刷后对kmp算法的理解感觉比一刷的时候深刻了不少啊??

class Solution {
public:
    void getNext(const string& s, vector& next) {
        int j = 0;
        next[0] = j;
        for (int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[j] == s[i]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0)return 0;
        vector next(needle.size() + 1, 0);
        getNext(needle, next);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size()) {
                return i - needle.size() + 1;
            }
        }
        return -1;
    }
};

相关

标签