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

做题思路 or 感想：

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

kmp算法的操作过程我觉得有句话很合适：KMP 算法永不回退 目标字符串 的指针 i，不走回头路（不会重复扫描 目标字符串），而是借助 next 数组中储存的信息把 模板字符串 移到正确的位置继续匹配
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
最后是利用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<int>& 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<int> 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;

    }

};

巴特西

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

做题思路 or 感想：

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

最新文章

热门文章

巴特西

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

做题思路 or 感想 ：

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

最新文章

热门文章

做题思路 or 感想：