Module: Função de prefixo, função Z


Problem

2 /10


função de prefixo

Theory Click to read/hide

Depois de otimizar a função de prefixo (para detalhes aqui ), obtemos o algoritmo final com O(n) assintótico:

vetor<int> função_prefixo (string s) {
int n = (int ) s.comprimento();
vetor<int>pi(n);
para (int i=1; i<n; ++i) {
int j = pi[i-1< /extensão>];
enquanto (j > 0 && s[i] != s[j])
j = pi[j-1];
se (s[i] == s[j]) ++j;
pi[i] = j;
}
retornarpi;
}

Problem

Dada uma string não vazia S cujo comprimento N não exceda \(10^6\). Assumiremos que os elementos da string são numerados de 1 a N.
 
Para cada posição do caractere i na string, estaremos interessados ​​na substring que termina naquela posição e corresponde a algum início de toda a string. De um modo geral, haverá várias dessas substrings, pelo menos duas. O maior deles tem o comprimento i, não estaremos interessados ​​nele. E estaremos interessados ​​na maior das substrings restantes (observe que tal substring sempre existe — no caso extremo, se nada mais for encontrado, uma substring vazia servirá).
 
O valor da função de prefixo \(\pi[i]\) será o comprimento desta substring.
 
A função de prefixo é usada em vários algoritmos de processamento de strings. Em particular, pode ser usado para resolver rapidamente o problema de encontrar a ocorrência de uma string em outra ("procurar um padrão no texto").
 
Necessário para todos os i de 1 a N para calcular \(\pi[i ] \).
 
Entrada
Uma string de comprimento N, \(0 < N <= 10^6\), consistindo em letras latinas minúsculas
 
Saída
Saída N números — valores de função de prefixo para cada posição, separados por espaços.
 

 

Exemplos
# Entrada Saída
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4

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!