实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll" 输出: 2 示例 2:

输入: haystack = "aaaaa", needle = "bba" 输出: -1 说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(s, t) {
    var i = 0,
        j = 0,
        next = [t.length];
    
    var x = 0, k = -1;
    next[0] = -1;
    while(x < t.length - 1){
        if(k == -1 || t[x] == t[k]){
            x++;
            k++;
            next[x] = k
        }else{
            k = next[k]
        }
    }
    while(i < s.length && j < t.length){
        if(j == -1 || s[i] == t[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j >= t.length){
        return i - t.length;
    }
    return -1;
};