Module: Función de prefijo, función Z


Problem

2 /10


función de prefijo

Theory Click to read/hide

Después de optimizar la función de prefijo (para detalles aquí ), obtenemos el algoritmo final con asintóticas O(n):

vector<int> función_prefijo (cadena s) {
int n = (int ) s.longitud();
vector<int>pi(n);
para (int i=1; i<n; ++i) {
int j = pi[i-1< /intervalo>];
mientras (j > 0 && s[i] != s[j])
j = pi[j-1];
si (s[i] == s[j]) ++j;
pi[i] = j;
}
regresarpi;
}

Problem

Dada una cadena no vacía S cuya longitud N no exceda \(10^6\). Asumiremos que los elementos de la cadena están numerados de 1 a N.
 
Para cada posición del carácter i en la cadena, nos interesará la subcadena que termina en esa posición y coincide con algún comienzo de la cadena completa. En términos generales, habrá varias subcadenas de este tipo, al menos dos. El más largo de ellos tiene la longitud i, no nos interesará. Y nos interesará la más larga de las subcadenas restantes (tenga en cuenta que tal subcadena siempre existe; en el caso extremo, si no se encuentra nada más, bastará con una subcadena vacía).
 
El valor de la función de prefijo \(\pi[i]\) será la longitud de esta subcadena.
 
La función de prefijo se usa en varios algoritmos de procesamiento de cadenas. En particular, se puede usar para resolver rápidamente el problema de encontrar la ocurrencia de una cadena en otra ("buscar un patrón en el texto").
 
Requerido para todos los i desde 1 a N para calcular \(\pi[i ] \).
 
Entrada
Una cadena de longitud N, \(0 < N <= 10^6\), que consta de letras latinas pequeñas .
 
Salida
Salida N números : valores de función de prefijo para cada posición, separados por espacios.
 

 

Ejemplos

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4