KMP (Knuth-Morris-Pratt) String matching program

KMP Algo

Reference: https://www.youtube.com/watch?v=4jY57Ehc14Y

// JS implementation
function KMP(arr, pat) {
    let arrLen = arr.length;
    let patLen = pat.length;
    let i=0, j=0;
    let lps = computeLPS(pat);
    while(i < (arrLen - patLen +1 )) {
        if(arr[i] == pat[j]) {
            i++;
            j++;
        } else {
            if(j != 0 ) {
                j = lps[j-1];
            } else {
                i++;
            }
        }
        if(j == patLen) {
            console.log("occurrence at", i - j);
            j = lps[j-1];
        }
    }
}

function computeLPS(pat) {
    let patLen = pat.length;
    let len = 0, i = 1;
    let lps = new Array(patLen).fill(0);
    while (i < patLen) {
        if(pat[i] == pat[len]) {
            lps[i] = len + 1;
            len++;
            i++;
        } else {
            if(len != 0) {
                len = lps[len-1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}