1function buildNext(pattern) {
2 const next = new Array(pattern.length).fill(0);
3 for (let i = 1, j = 0; i < pattern.length; i++) {
4 while (j > 0 && pattern[i] !== pattern[j]) j = next[j - 1];
5 if (pattern[i] === pattern[j]) j++;
6 next[i] = j;
7 }
8 return next;
9}
10function kmpSearch(text, pattern) {
11 const next = buildNext(pattern);
12 for (let i = 0, j = 0; i < text.length; i++) {
13 while (j > 0 && text[i] !== pattern[j]) j = next[j - 1];
14 if (text[i] === pattern[j]) j++;
15 if (j === pattern.length) return i - j + 1;
16 }
17 return -1;
18}