Algoritmo Z: búsqueda de patrón lineal

Dada una cadena text y un patrón pattern, implementa la Z-function para encontrar todas las posiciones de inicio (índice 0) donde pattern aparece en text en tiempo O(n + m).

¿Qué es la Z-function?

Para una cadena s de longitud n, el Z-array Z[i] almacena la longitud del segmento más largo que empieza en la posición i y que coincide con un prefijo de s.

Por convención Z[0] puede ser 0 o n (en este problema se deja 0).

Algoritmo de búsqueda

1. Construye la cadena concatenada s = pattern + "$" + text (el separador "$" no debe aparecer en ninguno de los dos).
2. Calcula el Z-array de s.
3. Toda posición i del Z-array donde Z[i] === pattern.length indica una ocurrencia en text que empieza en el índice i - pattern.length - 1.

Ejemplo

zFunction("abcabcabc", "abc")  // [0, 3, 6]
zFunction("aaa", "a")          // [0, 1, 2]
zFunction("hello", "xyz")      // []
zFunction("aaaa", "aa")        // [0, 1, 2]

Restricciones

• 1 ≤ text.length ≤ 100 000
• 1 ≤ pattern.length ≤ text.length
• Ambas cadenas contienen solo letras ASCII minúsculas.
• El carácter separador "$" no aparece en ninguna de las dos cadenas.
• La solución debe ser O(n + m) en tiempo y espacio.