Z-функция

1function zFunction(s: string): number[] {
2  const n = s.length
3  const z = [0]
4  let l = 0, r = 0 // самый правый z-бокс
5 
6  for (let i = 1; i < n; i++) {
7    if (i < r) z[i] = Math.min(r - i, z[i - l]!)
8    while (i + z[i]! < n && s[z[i]!] === s[i + z[i]!]) z[i]!
9    if (i + z[i]! > r) { l = i; r = i + z[i]! }
10  }
11 
12  return z
13}
14 
15function zSearch(text: string, p: string): number[] {
16  const z = zFunction(p + '#' + text)
17  return z.map((v, i) => (v === p.length ? i - p.length - 1 : -1))
18    .filter((i) => i >= 0)
19}