Манахер: палиндромы за O(n)

1function manacher(s: string): number[] {
2  // разделяем #a#b#a# — палиндромы любой чётности едины
3  const t = '#' + [...s].join('#') + '#'
4  const n = t.length
5  const p = new Array(n).fill(0) // p[i] — радиус палиндрома в i
6 
7  let c = 0, r = 0 // центр и край самого правого палиндрома
8  for (let i = 0; i < n; i++) {
9    if (i < r) p[i] = Math.min(r - i, p[2 * c - i]!) // зеркало
10    while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
11           t[i - p[i] - 1] === t[i + p[i] + 1]) p[i]!
12    if (i + p[i] > r) { c = i; r = i + p[i] }
13  }
14 
15  return p // длина палиндрома в исходной строке = p[i]
16}