dongnguyenltqb
6/23/2018 - 2:18 AM

z_algorithm.js

const z_algo=(s)=>{
    let n = s.length;
    var z = [n];
    let l=0,r=0;
    for (let i = 1; i < n; i++) {
        if (i > r) {
            l = r = i;
            while (r < n && s[r - l] == s[r]) r += 1;
            z[i] = r - l;
            r -= 1;
        } else if (z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        } else {
            l = i;
            while (r < n && s[r - l] == s[r]) r += 1;
            z[i] = r - l;
            r -= 1;
        }
    }
    return z;
}