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


Para resolver este problema, a enumeração usual não funcionará, porque sua assimptótica será O(t*s). Portanto, para tarefas de pesquisa de substring, o algoritmo KMP (Knuth-Morris-Pratt) é usado.
Para implementar este algoritmo, a função string prefix é usada, esta é uma matriz de números de comprimento n (strong>s comprimento), em que cada elemento é o  comprimento máximo do maior sufixo próprio da substring s, correspondente ao seu prefixo. Por exemplo:
 
Linha Função de prefixo Nota
abababcab 0 0 1 2 3 4 0 1 2  
abcabcd 0 0 0 1 2 3 0  
aabaaab 0 1 0 1 2 2 3  

Algoritmo de função de prefixo trivial com O(n^3) assintótico:

vetor<int> função_prefixo (string s) {
int n = (int ) s.comprimento();
vetor<int>pi(n);
para (int i=0; i<n; ++i)
para (int k=0; k<=i; ++k)
se (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
retornarpi;
}

E agora precisamos fazer uma função de prefixo para uma string no formato: & nbsp; t + # + s, onde # é um caractere delimitador que claramente não está no texto.  Analisando os valores da função de prefixo após o caractere separador correspondente, deve-se observar que, se o valor resultante for igual ao comprimento da substring desejada, sua ocorrência será encontrada. Por exemplo, para a string "abababcab" e a substring desejada "abab", a função do prefixo será:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 precisamos analisar os elementos da string correspondente s:
1 2 3 4 3 4 0 1 2 - há dois casos em que o valor é 4 (4º e 6º), ou seja, comprimento t,  como resultado, a resposta deve ser escrita: 4 - 4 (comprimento t) & nbsp; = 0 e 6 - 4 = 2. Pode-se ver que essas são as respostas corretas e a string "abab" é na verdade uma substring na string "abababcab" nas posições 0 e 2.

 

Training problem

(C++) Pesquisa de substring, KMP, variante trivial: Iniciar

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;
}

Training problem

função de prefixo

Z-função
Z-function da string S - array Z, cada elemento do qual é Z [i] é igual ao prefixo mais longo da substring começando na posição i na string S, que também é o prefixo de toda a string Z. O valor da função Z na posição zero é geralmente zero ou o comprimento de toda a string.
Dificuldade
O(|S| ^ 2) ou O(|S|).
 
Função de prefixo da string S - array P, cada elemento do qual P[i] é igual ao sufixo mais longo do substring iniciando na posição i na string S, que também é o sufixo da string inteira S. O valor da função P na posição zero é geralmente zero ou o comprimento de toda a string. 
Dificuldade
O(|S| ^ 2) ou O(|S|).
 
Tente implementar função Z e função de prefixo para O(|S| ^ 2) .

Training problem

função Z

 
Tanto Z quanto o prefixo da função podem ser usados ​​para implementar o algoritmo KMP(Knuth-Morris-Pratt) para encontrar uma substring em uma string em O(|S|). A essência desse algoritmo é a seguinte: atribuímos à string que queremos encontrar a string na qual estamos pesquisando. É altamente desejável colocar um caractere separador entre essas linhas, ou seja, um caractere que não ocorra em nenhuma linha (geralmente #).

Training problem

Cifra