Бойер-Мур

1function boyerMoore(text: string, p: string): number[] {
2  // таблица плохого символа: крайний правый индекс буквы в образце
3  const bad = new Map<string, number>()
4  ;[...p].forEach((ch, i) => bad.set(ch, i))
5 
6  const found: number[] = []
7  let i = 0
8  while (i + p.length <= text.length) {
9    let j = p.length - 1
10    while (j >= 0 && text[i + j] === p[j]) j-- // справа налево!
11    if (j < 0) {
12      found.push(i)
13      i++
14    } else {
15      // сдвиг по несовпавшей букве окна
16      const shift = Math.max(1, j - (bad.get(text[i + j]) ?? -1))
17      i += shift
18    }
19  }
20 
21  return found
22}