Função Z

Suponha que recebamos uma string $s$ de tamanho $n$. A função Z para essa string é uma array de tamanho $n$ onde o $i$-ésimo elemento é igual ao maior número de caracteres começando na posição $i$ que coincide com os primeiros caracteres de $s$.

Em outras palavras, $z[i]$ é o comprimento do prefixo comum mais longo entre $s$ e o sufixo de $s$ começando em $i$.

Nota: Neste artigo, o primeiro caractere de $s$ tem índice $0$ e o último índice $n-1$.

O primeiro elemento da função Z, $z[0]$, geralmente não é bem definido. Neste artigo, assumiremos que é zero (embora não mude nada na implementação do algoritmo).

Este artigo apresenta um algoritmo para calcular a função Z em tempo $O(n)$, bem como várias de suas aplicações.

Exemplos

Por exemplo, aqui estão os valores da função Z calculados para diferentes strings:

Algoritmo trivial

A definição formal pode ser representada na seguinte implementação elementar em $O(n^2)$.

vector<int> z_function_trivial(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1; i < n; ++i)
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
    return z;
}

Nós apenas iteramos sobre todas as posições $i$ e atualizamos $z[i]$ para cada uma delas, começando em $z[i] = 0$ e incrementando-a desde que não encontremos uma 'incompatibilidade' (e enquanto não chegamos ao fim da linha).

Algoritmo eficiente

Para obter um algoritmo eficiente, calcularemos os valores de $z[i]$ com $i = 1$ até $n - 1$ mas, ao mesmo tempo, ao calcular um novo valor, tentaremos fazer o melhor uso possível dos valores calculados anteriormente.

Por uma questão de sermos breves, vamos chamar correspondências de segmento àquelas substrings que coincidem com um prefixo de $s$. Por exemplo, o valor da função Z desejada $z[i]$ é o comprimento do segmento correspondendo ao começo da posição $i$ (e isso termina na posição $i + z[i] - 1$).

Para fazer isso, manteremos os índices $[l; r]$ do segmento mais à direita correspondem. Ou seja, entre todos os segmentos detectados, manteremos o que terminar mais à direita. De certa forma, o índice $r$ pode ser visto como o "limite" para o qual nossa string $s$ foi varrida pelo algoritmo; tudo além desse ponto ainda não é conhecido.

Então, se o índice atual (para o qual temos que calcular o próximo valor da função Z) for $i$, teremos uma das duas opções:

Assim, todo o algoritmo é dividido em dois casos, que diferem apenas no valor inicial de $z[i]$: no primeiro caso, assume-se zero, no segundo caso, é determinado pelos valores computados anteriormente (usando a fórmula acima). Depois disso, ambas as ramificações desse algoritmo podem ser reduzidas à implementação do algoritmo trivial, que inicia imediatamente após a especificação do valor inicial.

O algoritmo acaba sendo muito simples. Apesar do fato de que em cada iteração o algoritmo trivial é executado, fizemos um progresso significativo, tendo um algoritmo que é executado em tempo linear. Depois provaremos que o tempo de execução é linear.

Implementação

A implementação acaba sendo bastante curta:

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

Comentários sobre esta implementação

oda a solução é dada como uma função que retorna uma array de comprimento $n$ -- a função Z de $s$.

Array $z$ é inicialmente preenchida com zeros. O segmento de correspondência mais à direita atual é assumido como $[0; 0]$ (um segmento pequeno que não contém nenhum $i$).

Dentro do loop for $i = 1 \dots n - 1$ primeiro determinamos o valor inicial $z[i]$ -- ele permanecerá zero ou será computado usando a fórmula acima.

Posteriormente, o algoritmo trivial tenta aumentar o valor de $z[i]$ o máximo possível.

No final, se for necessário (ou seja, se $i + z[i] - 1 > r$), atualizamos o segmento de correspondência mais à direita $[l; r]$.

Comportamento assintótico do algoritmo

Vamos provar que o algoritmo acima tem um tempo de execução linear no comprimento da string - portanto, é $O(n)$.

Estamos interessados ​​no loop while, já que todo o resto é apenas um monte de operações constantes que somam $O(n)$.

Mostraremos que cada iteração do loop while aumentará a borda direita $r$ do segmento de correspondência.

Para fazer isso, consideraremos os dois ramos do algoritmo:

Portanto, provamos que cada iteração do loop interno faz o ponteiro $r$ avançar para a direita. Como $r$ não pode ser superior a $n-1$, isso significa que o loop interno não fará mais do que $n-1$ iterações.

Como o restante do algoritmo obviamente funciona em $O(n)$, provamos que todo o algoritmo para calcular funções Z é executado em tempo linear.

Aplicações

amos agora considerar alguns usos das funções Z para tarefas específicas.

Esses aplicações serão amplamente similares aos da função de prefixos.

Procure a substring

Para simplificar, chamamos $t$ a string de texto, e $p$ o padrão. O problema é: encontre todas as ocorrências do padrão $p$ dentro do texto $t$.

TPara resolver esse problema, criamos uma nova string $s = p + \diamond + t$, ou seja, aplicamos a concatenação das string $p$ e $t$ mas também colocamos um caractere separador $\diamond$ no meio (escolhemos $\diamond$ para que ele certamente não esteja presente em nenhum lugar nas strings $p$ ou $t$).

Calcule a função-z para $s$. Então, para qualquer $i$ no intervalo $[0; \; \operatorname{length}(t) - 1]$, iremos considerar o valor correspondente $k = z[i + \operatorname{length}(p) + 1]$. Se $k$ for igual $\operatorname{length}(p)$ sabemos que há uma ocorrência de $p$ na $i$-ésima posição de $t$, caso contrário, não há ocorrência.

O tempo de execução (e consumo de memória) é $O(\operatorname{length}(t) + \operatorname{length}(p))$.

Número de substrings distintas em uma string

Dada uma string $s$ de tamanho $n$, conte o número de substrings distintas de $s$.

Vamos resolver esse problema iterativamente. Ou seja: conhecendo o número atual de diferentes substrings, recalcule esse valor após adicionar um caractere ao final de $s$.

Portanto, seja $k$ o número atual de substrings distintas de $s$. Anexamos um novo caractere $c$ a $s$. Obviamente, pode haver algumas novas substrings terminando neste novo caractere $c$ (ou seja, todas as strings que terminam com esse símbolo e que ainda não encontramos).

Pegue uma string $t = s + c$ e inverta-a (escreva seus caracteres na ordem inversa). Nossa tarefa agora é contar quantos prefixos de $t$ não são encontrados em nenhum outro lugar em $t$. Vamos calcular a função-Z de $t$ e encontrar seu valor máximo $z_{max}$. Obviamente, o prefixo de $t$ de tamanho $z_{max}$ ocorre também em algum lugar no meio de $t$. Claramente, prefixos mais curtos também ocorrem.

Portanto, descobrimos que o número de novas substrings que aparecem quando o símbolo $c$ é anexado a $s$ é igual a $\operatorname{length}(t) - z_{max}$.

Consequentemente, o tempo de execução desta solução é $O(n^2)$ para uma string de tamanho $n$.

Vale ressaltar que, exatamente da mesma maneira, podemos recalcular(ainda em tempo $O(n)$), o número de substrings distintas ao anexar um caractere no início da string, bem como ao removê-lo (do final ou o início).

Comprimindo uma string

Dada uma string $s$ de tamanho $n$. Encontre sua representação "compactada" mais curta, ou seja: encontre uma string $t$ de menor tamanho, de modo que $s$ possa ser representado como uma concatenação de uma ou mais cópias de $t$.

Uma solução é: calcular a função Z de $s$, percorrer todos os $i$'s de modo que $i$ divida $n$. Pare no primeiro $i$ em que $i + z[i] = n$. Então, a string $s$ pode ser comprimida no tamanho $i$.

A prova desse fato é a mesma da solução que usa a função de prefixos.

Problemas