45 lines
1.0 KiB
JavaScript
45 lines
1.0 KiB
JavaScript
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") |