问题描述
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
思路分析
借此题回顾一下KMP算法！
其实KMP算法之前看过无数次了，但这次看了这篇博文里面的图，才真正理解了KMP算法中next数组的求法！总结一下。
KMP算法解决的问题是在字符串s1（长度n）中的查找字符串s2（长度m）。暴力的方法是枚举s的位置i，试图从i位置开始匹配p。这样的方法复杂度为O(nm)。
KMP的出发点是，如果s2具有一定的特点，那么不用每次都从s2的头部重新开始匹配。假设在s2的j位置处，s2与s1失配，说明s2在j位置前与s1都是匹配的，这个信息可以被利用。例如主串是“abababc”，子串是“ababc”，若i, j=4，即在s2的‘c’和s1的‘a’处失配，那么说明前面的“abab”已经匹配了，那么我们可以直接将s2后移两位，即j -= 2，让s2从j=2处和s1的i=4处继续匹配。
这样做的好处是，s1是不回溯的，永远在往前搜，平均复杂度降到了O(n+m)。
那么如何确定每次j需要如何移动呢？即我们要求一个next数组，next[j]代表s2在j处于如果失配，下一个应该尝试和s1匹配的是next[j]处的字符。
注：其实我发现网上对next数组的定义是有不同版本的，有的定义与我这里相同，即下一个应该尝试的位置，而有的是定义为j及j以前的字符串最长前缀和后缀重叠数，其实本质是相同的而且可以相互转换，个人觉得我采取的这种定义可以直接用到匹配函数里，比较方便。
next数组的求法
首先，next[0]和next[1]都是0，因为在j=0和1的位置之前的匹配成功信息不能产生什么帮助；
然后我们假设我们已经求出next[0...j-1]，我们下面要求next[j]。
设next[j-1] = k。
由图示可知，A1==A2，如果s2[j-1] == s[k]，那么next[j] = k + 1；
s2[j-1] ！= s[k]，那么就要找有没有更短一点的字符串可以利用。由A1==A2，B1==B2可以推断，B2==B3，且B2是可以考虑的前缀串里最长的了，因为如果有更长的，next[k]就不会在这个位置了。于是在这里要判断的是s2[j-1] == s[next[k]]，如果成立，那么next[j] = next[k] + 1，如果不满足，则考虑更短一些的C2（对应next[next[k]]），可以看出这是一个迭代的过程，当然k最小就是0啦。
求完next数组，kmp算法就没有什么难度了，暴力匹配时，当在j处失败时，j重新返回0，在KMP里改成返回next[j]位置即可。
附上28题AC代码
class Solution {
public:
vector<int> getNext (string s){
int n = s.size();
vector<int> next(n);
next[0] = 0;
if (n == 1)
return next;
next[1] = 0;
int k = 0;
for (int i = 2; i < n; i++){
while (k > 0 && s[i-1] != s[k])
k = next[k];
if (s[i-1] == s[k])
k += 1;
next[i] = k;
}
return next;
}
int strStr(string s1, string s2){
int i = 0;
int j = 0;
int len1 = s1.size();
int len2 = s2.size();
if (len2 == 0)
return 0;
vector<int> next = getNext(s2);
while (i < len1 && j < len2){
if (len1 - i < len2 - j)
break;
if (s1[i] == s2[j]){
++i;
++j;
}
else{
if (j == 0)
++i;
else
j = next[j];
}
}
if (j == len2)
return i - len2;
else
return -1;
}
};
Runtime: 6 ms, which beats 30.20% of cpp submissions.
