KMP算法看了好多次，看一次忘一次，而且以前也没有深究一些东西。这次记录一下。
先是求next数组，
即最长相同前后缀长度。例如abcab，ab就是最长相同前后缀。。
用双指针法，j在后，k在前。next[j]代表的是j之前（不包括needle[j]）的最长相同前后缀长度-1（-1是为了便于跳转）
求的时候主要有几种情况：
needle[j] == needle[k]：
相等的话needle[0...k] == need[j-k...j]，因此next[j+1] = k+1;
k == -1：
特殊边界判断
needle[j] != needle[k]：
needle[0...k-1] == needle[j-k...j-1]，next[j+1] < k，
因此k = next[k]回退快速找到相同前后缀。
完整代码书写
此时得到了next数组，再利用双指针i,j。i是永远不会回退的。
两个指针指向字符相同时，当然一起++就行了，
不同时，就j = next[j]，再继续比较。
说一下注意点：
1、考虑字符串为空的情况
2、求next数组时一开始要给next[0]赋值：next[0] = -1;
3、size()转化为int比较，老是忘。。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle == "")
{
return 0;
}
vector<int> next = GetNext(needle);
int i = 0, j = 0, hlen=haystack.size(), nlen=needle.size();
while (i < hlen && j < nlen)
{
if (j == -1 || haystack[i] == needle[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j == needle.size())
{
return i-j;
}
else
{
return -1;
}
}
vector<int> GetNext(string needle)
{
vector<int> next(needle.size());
int j = 0, k = -1, nlen = needle.size();
next[0] = -1;
while (j < nlen - 1)
{
if (k == -1 || needle[j] == needle[k])
{
++j;
++k;
next[j] = k;
}
else
{
k = next[k];
}
}
return next;
}
};