Рабин-Карп

1function rabinKarp(text: string, pattern: string): number[] {
2  const base = 256, mod = 101
3  const m = pattern.length
4  const found: number[] = []
5 
6  let ph = 0, th = 0
7  for (let i = 0; i < m; i++) {
8    ph = (ph * base + pattern.charCodeAt(i)) % mod
9    th = (th * base + text.charCodeAt(i)) % mod
10  }
11 
12  for (let i = 0; i + m <= text.length; i++) {
13    if (th === ph && text.slice(i, i + m) === pattern) found.push(i)
14    // скользящий пересчёт: выкидываем левую букву, добавляем правую
15    if (i + m < text.length) {
16      th = (th - text.charCodeAt(i) * base ** (m - 1)) * base
17      th = (th + text.charCodeAt(i + m)) % mod
18    }
19  }
20 
21  return found
22}