leetcode28. Implement strStr() (以及个人对KMP算法理解) 算法与数据结构

kmp算法标准板子题

class Solution { public: vector getNext(string needle) { vector next(needle.length()); int k = -1 ; int j = 0; next[0] = -1; while(j < needle.length()-1) { if(k == -1 || needle[j] == needle[k]) next[++j] = ++k; else k = next[k]; } return next; }int strStr(string haystack, string needle) { int m = haystack.length(); int n = needle.length(); if(n == 0) return 0; int i = 0, j = 0; vector next = getNext(needle); while(i < m && j < n) { if(j == -1 || haystack[i] == needle[j]) { i++; j++; } else j = next[j]; } if(j == n) return i - j; else return -1; } };

在这里记录一下KMP算法的理解
1.KMP是什么
对于主串a搜素子串b的问题：
【leetcode28. Implement strStr() (以及个人对KMP算法理解)】暴力搜索的复杂度为O(主串长度*模式串长度)

文章图片

暴力搜索就是a[i] != b[j]时
j = 0;
i = i - j + 1;
这样做效率极低。
如果利用KMP来做，时间复杂度O(m+n)为线性复杂度，已经是最低的了
2.KMP为什么这么做
以下面这个图为例，KMP算法的核心在于，当最后一位C与D无法匹配时，这时候有个隐含信息，就是匹配串的前三位ABA已经和主串的对应三位ABA匹配过，可能留下了一些匹配信息
如果拿之前的暴力搜索来看，最后一位C与D无法匹配时，

文章图片

j会重置为0，i会变为1

文章图片

B与A不匹配，j重置，i变为2;

文章图片

然后比较B与C
像j=0与i=1匹配不上再移位的这种操作耗费了大量时间，我们能不能直接跳到上面这张j=0与i=2的比较图呢？
答案是肯定的，KMP算法就是利用了这个特性，当模式串的某一位不再匹配时，对于模式串不用重新从0开始，而是让i不变，j之前的模式串与主串刚好匹配就行。这样就省略了暴力搜索中需要j归零的操作。
3.KMP具体怎么做：
难点在于得出当子字符串的某一位无法匹配时，j变为多少
其实稍微分析一下就能看出结果
1.模式串的第一位就与主串不匹配，这时候需要原字符串的指针右移,用j = -1来表示，主要程序遇到j=-1表示i需要右移了。
2.模式串的第二位不匹配，j需要归零
3.模式串的第j位不匹配(j>1)，这个时候就用了下面的这个公式进行递推

next[0] = -1; while(j < s.length()-1) { if(k == -1 || s[j] == s[k]) next[++j] = ++k; else k = next[k]; }

这个公式的具体解释可见https://www.cnblogs.com/yjiyjige/p/3263858.html
换句话说，如果前一位字符和前一位要跳转到的字符相同，那么后面这一位的跳转位置就是前一位的跳转位置+1;
好了，现在知道这个对我们找出每一位的跳转位置有什么用呢？
对于前一位字符和前一位要跳转到的字符相同的情况，可以直接利用下面的公式进行递推

if(k = next[j] && s[k] == s[j]) next[j+1] = k + 1;

对于s[k]与s[j]不相等的情况，上面贴出来的这篇文章根本没讲清楚。

文章图片

我们可以这样想，首先next[j+1]肯定不在C的后面，可以用反证法证明：
假如在C的后面，那么j+1的前面一定是ABAC.......ABAB,这个与之前的next[j] = k矛盾，因为最长的前缀是ABA而不是ABAC......ABA,所以，next[j+1]可能的位置一定在C的前面
然后，这时候就是模式串ABAC与被匹配串ABAB....的最后一位冲突了而需要移位寻找BAB,AB或B的情况,所以
k = next[k]
5.关于为什么KMP算法不好理解的个人感受
KMP算法其实经历了好几个难点，只不过很多地方没把这些难点讲清楚。
暴力搜索的优化（难点1）
匹配失败后指针所移动到的位置的计算（难点2）
s[k]与s[j]不相等时next[++j]的计算(难点3)