Кнут-Моррис-Пратт (KMP)

1function buildPrefixFunction(p: string): number[] {
2  const pi = [0]
3  let k = 0
4 
5  for (let i = 1; i < p.length; i++) {
6    while (k > 0 && p[i] !== p[k]) k = pi[k - 1]!
7    if (p[i] === p[k]) k++
8    pi[i] = k
9  }
10 
11  return pi
12}
13 
14function kmpSearch(text: string, p: string): number[] {
15  const pi = buildPrefixFunction(p)
16  const found: number[] = []
17  let k = 0
18 
19  for (let i = 0; i < text.length; i++) {
20    while (k > 0 && text[i] !== p[k]) k = pi[k - 1]!
21    if (text[i] === p[k]) k++
22    if (k === p.length) {
23      found.push(i - p.length + 1)
24      k = pi[k - 1]!
25    }
26  }
27 
28  return found
29}