SOURCE

class Kmpa {
    nextArr = []
    constructor(txt, pat) {
        this.txt = txt
        this.pat = pat
    }

    forceFind() {
        let txtLen = this.txt.length
        let patLen = this.pat.length
        let index = -1
        for (let i = 0; i <= txtLen - patLen; i++) {
            let match = true
            for (let j = 0; j < patLen; j++) {
                if (this.txt[i+j] === this.pat[j]) {
                } else {
                    match = false
                    break
                }
            }
            if (match) {
                index = i
                break
            }
        }
        console.log(index)
        return index
    }

    getNextArr() {
        this.nextArr = [0]
        let now = this.nextArr[0]
        for (let i = 1; i < this.pat.length; i++) {
            if (this.pat[i] === this.pat[now]) {
                this.nextArr[i] = now + 1
                now = this.nextArr[i]
            } else {
                now = this.nextArr[i-1]
                this.nextArr[i] = now
            }
        }
    }

    findPatIndex() {
        this.getNextArr()
        console.log(this.nextArr)
        let txtLen = this.txt.length
        let patLen = this.pat.length
        let index = -1
        let moveLen = 0
        for (let i = 0; i < txtLen; i++) {
            if (this.txt[i] === this.pat[i - moveLen]) {
                if (i - moveLen === patLen - 1) {
                    return moveLen
                }
            } else {
                let k = this.nextArr[(i - moveLen - 1) < 0 ? 0 : i - moveLen - 1]
                moveLen = moveLen + (i - moveLen - k  + 1)
            }
        }
        console.log(moveLen)
        return -1
    }
}

const instance = new Kmpa('abddababdababcdcd778999', 'abcd')
instance.forceFind()
instance.findPatIndex()