const genNext = (str) => {
    const n = str.length
    const next = new Array(n).fill(0)
    next[0] = -1
    next[1] = 0
    for (let i = 2; i < n; i++) {
        const Letter = str[i - 1] //now we want to find that something equal to Letter
        let nextValue = i - 1
        while (nextValue >= 0) {
            if (Letter == str[next[nextValue]]) { //find
                break
            } else {
                nextValue = next[nextValue]
            }
        }
        if (nextValue == -1) {
            next[i] = 0
        } else {
            next[i] = next[nextValue] + 1
        }
    }
    return next
}

const kmp = (x, y) => {
    const next = genNext(y)
    console.log(next)
    const n = x.length
    const m = y.length
    let i = 0, j = 0
    while (i < n) {
        while (j > -1 && x[i] != y[j]) {
            j = next[j]
        }
        i++
        j++
        if (j == m) {
            console.log(i - j)
            j = 0 //when we have matched one, j should be zero
        }

    }
}

kmp("coniyconix", "conix")