题目：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
思路1：暴力匹配
假设haystack="abcabcx"，needle="abcabx"，m为haystack的长度，n为needle的长度， i为字符串haystack的索引，j为字符串needle的索引，依次比较haystack[i]和needle[j]，如下图：
回溯两个指针，重新比较，直到needle完全匹配上或haystack字符串循环结束也没有匹配上为止，如下图。
暴力匹配方法需要不停的回溯两个指针，时间复杂度为O(m*n)。
思路2：kmp算法
我们先观察一下上面第一次不匹配时的情况，为了清晰标注了一下颜色：
不匹配字符前面的ab(绿色)是已知匹配上的，恰好needle最前面的两个字符也是ab(红色)，
这提示我们可以设法利用红色ab和绿色ab相等来减少匹配的次数。我们可以把j直接移动到红色ab的下一个字符，i保持不动，继续进行匹配，如下图：
继续进行匹配，如果再遇到不匹配字符，重复上述步骤，直到needle完全匹配上，或者haystack字符串循环结束也没有匹配上为止，如下图：
这样不用回溯i，大大节省了效率。
把上面的步骤用代码实现：
var strStr = function(haystack, needle) {
var m = haystack.length, n = needle.length;
if(!n) return 0;
var next = kmpProcess(needle);
for(var i = 0, j = 0; i < m;) {
if(haystack[i] == needle[j]) { // 字符匹配，i和j都向前一步
i++, j++;
}
if(j == n) return i - j; // needle完全匹配上，返回匹配位置
if(haystack[i] != needle[j]) { // 字符不匹配
if(j > 0) {
// TODO 如何重置j呢？
} else {
i++;
}
}
}
return -1;
};
那么字符不匹配时，怎样让程序知道应该把j重置在什么地方呢？我们先来观察一下第一次不匹配时的情况：
此时在不匹配字符x前，needle的子串是：abcab，通过肉眼观察，前缀ab和后缀ab相等，字符串"ab"的长度是2，这时我们要把j重置到needle数组下标为2的地方(数组下标从0开始)。可以按照这个思路把needle中每个字符不匹配时，重置j的位置对应的记录到一个数组next里，我们接下来要做的就是求出next数组。
接下来我们开始计算next数组。最差的情况就是j重置到0，先把数组用0填充。
假设x是遍历needle的索引，y是neddle数组从0开始的索引，也是j将要重置的位置(即存入next数组的值)。因为needle的第一个字符没有前后缀，所以next[0]永远是0，所以x从1开始。计算next的过程如下：
- needle[x] != neddle[y]，由于y=0，所以next[x]=0，并且x向前一步，如下图：
2.needle[x] != neddle[y]，由于y=0，所以next[x]=0，并且x向前一步，如下图：
-
needle[x] == neddle[y]，如下图：
-
needle[x] == neddle[y]，如下图：
5.needle[x] != neddle[y]，由于y != 0，说明之前有匹配上的字符串，此时需要移动y至next[y-1]，即y=0，再去比较needle[x] 与 neddle[y]，注意，y !=0 或者needle[x] != neddle[y]时，x不能前进，要保持在原地，如下图：
最后得到next数组为：[0, 0, 0, 1, 2, 0]
把上面两步用代码实现：
var strStr = function(haystack, needle) {
var m = haystack.length, n = needle.length;
if(!n) return 0;
var next = kmpProcess(needle);
for(var i = 0, j = 0; i < m;) {
if(haystack[i] == needle[j]) { // 字符匹配，i和j都向前一步
i++, j++;
}
if(j == n) return i - j; // needle完全匹配上，返回匹配位置
if(haystack[i] != needle[j]) { // 字符不匹配
if(j > 0) {
j = next[j - 1]; // 重置j
} else {
i++;
}
}
}
return -1;
};
var kmpProcess = function(needle) {
var y = 0;
var x = 1;
var next = new Array(needle.length).fill(0);
while (x < needle.length) {
if (needle[x] == needle[y]) {
y++;
next[x] = y;
x++;
} else if (y > 0) {
y = next[y - 1];
} else {
next[x] = 0;
x++;
}
}
return next;
}
console.log(strStr('abcabcabya', 'abcaby')); // 3
kmpProcess的时间复杂度是O(n)，不需要回溯haystack的索引i，整个算法的时间复杂度为O(m+n)。
