SOURCE

// 暴力匹配算法
function brute_force(text, pattern) {
    for(let i = 0; i < text.length; i++) {
        let flag = 1;
        for(let j = 0; j < pattern.length; j++) {
            if(text[i + j] === pattern[j]) continue;
            flag = 0;
            break;
        }
        if(flag) return i;
    }
    return -1;
}

console.log(brute_force('hello','ell'))

// KMP 算法
function GetNext(pattern, next) {
    next[0] = -1;
    for(let i = 1, j = -1; i < pattern.length; ++i) {
        // 不相等时 j 往前跳
        while(j != -1 && pattern[j + 1].charCodeAt() - pattern[i].charCodeAt()) j = next[j];
        if(pattern[j + 1] == pattern[i]) j += 1;
        next[i] = j;
    }
    return ;
}

function kmp(text, pattern) {
    let n = pattern.length;
    let next = new Array(n)
    // 通过模式串 预处理出来向前跳的信息
    GetNext(pattern, next);
    for(let i = 0, j = -1; i < text.length; i++) {
        while(j != -1 && text[i].charCodeAt() - pattern[j + 1].charCodeAt()) j = next[j];
        if(text[i].charCodeAt() == pattern[j + 1].charCodeAt()) j += 1;
        // 判断是否匹配成功，j位置匹配成功的最后一位，如果j+1 为undefined 即匹配成功
        if(pattern[j + 1] == undefined) return i - j; 
    }
    return -1;
}
console.log(kmp('hello','ell'))