Função de prefixo - Algoritmo de Knuth – Morris – Pratt

Definição

Você recebe uma string $s$ de tamanho $n$. A função prefixo para essa string é definida como uma array $\pi$ de tamanho $n$, onde $\pi[i]$ é o comprimento do prefixo apropriado mais longo da substring $s[0 \dots i]$ que também é um sufixo dessa substring. Um prefixo adequado de uma string é um prefixo que não é igual à própria string. Por definição, $\pi[0] = 0$.

Matematicamente, a definição da função de prefixo pode ser escrita da seguinte maneira:

$$\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$$

Por exemplo, a função de prefixo da string "abcabcd" será $[0, 0, 0, 1, 2, 3, 0]$, e o prefixo da string "aabaaab" é $[0, 1, 0, 1, 2, 2, 3]$.

Algoritmo Trivial

Um algoritmo que segue exatamente a definição da função de prefixo é o seguinte:

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k <= i; k++)
            if (s.substr(0, k) == s.substr(i-k+1, k))
                pi[i] = k;
    return pi;
}

É fácil ver que sua complexidade é $O(n^3)$, que tem espaço para melhorias.

Algoritmo eficiente

Esse algoritmo foi proposto por Knuth e Pratt e, independentemente deles, por Morris em 1977. Foi usado como a principal função de um algoritmo de busca de substring.

Primeira otimização

A primeira observação importante é que os valores da função prefixo só podem aumentar em no máximo um.

De fato, caso contrário, se $\pi[i + 1] \gt \pi[i] + 1$, podemos pegar esse sufixo terminando na posição $i + 1$ com o comprimento $\pi[i + 1]$ e remova o último caractere dele. Terminamos com um sufixo que termina na posição $i$ com o comprimento $\pi[i + 1] - 1$, que é melhor que $\pi[i]$, ou seja, temos uma contradição.

A ilustração a seguir mostra essa contradição. O sufixo apropriado mais longo na posição $i$ que também é um prefixo de tamanho $2$, e na posição $i+1$ é de tamanho $4$. Portanto, a string $s_0 ~ s_1 ~ s_2 ~ s_3$ é igual à string $s_{i-2} ~ s_{i-1} ~ s_i ~ s_{i+1}$, o que significa que também as strings $s_0 ~ s_1 ~ s_2$ e $s_{i-2} ~ s_{i-1} ~ s_i$ são iguais, portanto, $\pi[i]$ deve ser $3$. $$\underbrace{\overbrace{s_0 ~ s_1}^{\pi[i] = 2} ~ s_2 ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{s_{i-2} ~ \overbrace{s_{i-1} ~ s_{i}}^{\pi[i] = 2} ~ s_{i+1}}_{\pi[i+1] = 4}$$

Assim, ao passar para a próxima posição, o valor da função prefixo pode aumentar em um, permanecer o mesmo ou diminuir em alguma quantidade. Esse fato já nos permite reduzir a complexidade do algoritmo para $O(n^2)$, porque em uma etapa a função prefixo pode crescer no máximo em um. No total, a função pode crescer no máximo $n$ etapas e, portanto, também pode apenas diminuir um total de $n$ etapas. Isso significa que precisamos executar $O(n)$ comparações de string, e alcançar a complexidade de $O(n^2)$.

Segunda otimização

Vamos além: queremos nos livrar das comparações de strings. Para conseguir isso, precisamos usar todas as informações calculadas nas etapas anteriores.

Então, vamos calcular o valor da função de prefixo $\pi$ para $i + 1$. Se $s[i+1] = s[\pi[i]]$, então podemos dizer com certeza que $\pi[i+1] = \pi[i] + 1$, pois já sabemos que o sufixo na posição $i$ de tamanho $\pi[i]$ é igual ao prefixo de tamanho $\pi[i]$. Isso é ilustrado novamente com um exemplo. $$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 = s_i + 1}}_{\pi[i+1] = \pi[i] + 1}$$

Se isso não for o caso, $s[i+1] \neq s[\pi[i]]$, então precisamos tentar uma string mais curta. Para acelerar as coisas, gostaríamos de passar imediatamente para o maior comprimento $j \lt \pi[i]$, de modo que a propriedade do prefixo na posição $i$ seja mantida, ou seja, $s[0 \dots j-1] = s[i-j+1 \dots i]$: $$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$$

De fato, se encontrarmos esse tamanho $j$, então, novamente, precisamos apenas comparar os caracteres $s[i+1]$ e $s[j]$. Se forem iguais, podemos atribuir $\pi[i+1] = j + 1$. Caso contrário, precisaremos encontrar o maior valor menor que $j$, para o qual a propriedade do prefixo é válida, e assim por diante. Pode acontecer que isso vá até $j = 0$. Se $s[i+1] = s[0]$, definimos $\pi[i+1] = 1$, e $\pi[i+1] = 0$ caso contrário.

Portanto, já temos um esquema geral do algoritmo. A única questão que resta é como podemos encontrar efetivamente os comprimentos de $j$. Vamos recapitular: para o comprimento atual $j$ na posição $i$ na qual a propriedade do prefixo é válida, ou seja, $s[0 \dots j-1] = s[i-j+1 \dots i]$, queremos encontrar o maior $k \lt j$, para o qual a propriedade do prefixo é válida. $$\overbrace{\underbrace{s_0 ~ s_1}_k ~ s_2 ~ s_3}^j ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_k}^j ~s_{i+1}$$

A ilustração mostra que esse deve ser o valor de $\pi[j-1]$, que já calculamos anteriormente.

Algoritmo final

Finalmente, podemos construir um algoritmo que não realiza comparações de strings e apenas executa $O(n)$ ações.

Aqui está o procedimento final:

Implementação

A implementação acaba sendo surpreendentemente curta e expressiva.

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

Este é um algoritmo online, ou seja, ele processa os dados à medida que chegam - por exemplo, você pode ler os caracteres da string um por um e processá-los imediatamente, localizando o valor da função de prefixo para cada próximo caractere. O algoritmo ainda exige o armazenamento da própria string e dos valores calculados anteriormente da função de prefixo, mas se soubermos previamente o valor máximo $M$ ue a função de prefixo pode assumir na string, podemos armazenar apenas $M+1$ primeiros caracteres da string e o mesmo número de valores da função prefixo.

Aplicações

Procure uma substring em uma string - Algoritmo de Knuth-Morris-Pratt

A tarefa é a aplicação clássica da função prefixo.

Dado um texto $t$ e uma string $s$, queremos encontrar e exibir as posições de todas as ocorrências da string $s$ no texto $t$.

Por conveniência, denotamos como $n$ o comprimento da string s e como $m$ o tamanho do texto $t$.

Geramos a string $s + \# + t$, onde $\#$ é um separador que não aparece em $s$ e $t$. Vamos calcular a função de prefixo para essa string. Agora pense no significado dos valores da função prefixo, exceto pelas primeiras $n + 1$ entradas (nas quais pertencem a string $s$ e o separador). Por definição, o valor $\pi[i]$ mostra o maior comprimento de uma substring que termina na posição $i$ que coincide com o prefixo. Mas, no nosso caso, isso nada mais é do que o maior bloco que coincide com $s$ e termina na posição $i$. Esse comprimento não pode ser maior que $n$ devido ao separador. Mas se a igualdade $\pi[i] = n$ for alcançada, isso significa que a string $s$ aparece completamente nessa posição, ou seja, termina na posição $i$. Apenas não esqueça que as posições são indexadas na string $s + \# + t$.

Portanto, se em alguma posição $i$ tivermos $\pi[i] = n$, então, na posição $i - (n + 1) - n + 1 = i - 2n$ na string $t$, a string $s$ aparece.

Como já mencionado na descrição da computação da função de prefixo, se sabemos que os valores do prefixo nunca excedem um determinado valor, não precisamos armazenar a string inteira e a função inteira, mas apenas o seu início. No nosso caso, isso significa que precisamos armazenar apenas a string $s + \#$ e os valores do prefixo para ela. Podemos ler um caractere de cada vez da string $t$ e calcular o valor atual da função de prefixo.

Assim, o algoritmo Knuth-Morris-Pratt resolve o problema em tempo $O(n + m)$ com $O(n)$ de memória.

Contando o número de ocorrências de cada prefixo

Aqui discutimos dois problemas ao mesmo tempo. Dada uma string $s$ de tamanho $n$. Na primeira variação do problema, queremos contar o número de ocorrências de cada prefixo $s[0 \dots i]$ na mesma string. Na segunda variação do problema, outra string $t$ é fornecida e queremos contar o número de ocorrências de cada prefixo $s[0 \dots i]$ em $t$.

Primeiro resolvemos o primeiro problema. Considere o valor da função de prefixo $\pi[i]$ em uma posição $i$. Por definição, significa que na posição $i$ o prefixo de tamanho $\pi[i]$ da string $s$ aparece e termina na posição $i$, e não existe um prefixo mais longo que siga essa definição. Ao mesmo tempo, prefixos mais curtos podem terminar nesta posição. Não é difícil ver que temos a mesma pergunta que já respondemos quando calculamos a própria função de prefixo: Dado um prefixo de comprimento $j$ que é um sufixo que termina na posição $i$, qual é o próximo prefixo menor $\lt j$ que também é um sufixo que termina na posição $i$. Assim, na posição $i$ termina o prefixo de comprimento $\pi[i]$, o prefixo de comprimento $\pi[\pi[i] - 1]$, o prefixo $\pi[\pi[\pi[i] - 1] - 1]$, e assim por diante, até o índice se tornar zero. Assim, podemos calcular a resposta da seguinte maneira.

vector<int> ans(n + 1);
for (int i = 0; i < n; i++)
    ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
    ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
    ans[i]++;

Aqui, para cada valor da função de prefixo, contamos primeiro quantas vezes ocorre na array $\pi$, e depois calculamos as respostas finais: se sabemos que o prefixo de comprimento $i$ aparece exatamente $\text{ans}[i]$ vezes, então, esse número deve ser adicionado ao número de ocorrências de seu sufixo mais longo, que também é um prefixo. No final, precisamos adicionar $1$ a cada resultado, pois também precisamos contar os prefixos originais.

Agora vamos considerar o segundo problema. Aplicamos o truque de Knuth-Morris-Pratt: criamos a string $s + \# + t$ e calculamos sua função de prefixo. As únicas diferenças para a primeira tarefa é que estamos interessados ​​apenas nos valores do prefixo relacionados à string $t$, ou seja, $\pi[i]$ para $i \ge n + 1$. Com esses valores, podemos realizar exatamente os mesmos cálculos que na primeira tarefa.

O número de diferentes substrings em uma string

Dada uma string $s$ de tamanho $n$. Queremos calcular o número de diferentes substrings que aparecem nele.

Vamos resolver esse problema iterativamente. Iremos ver, sabendo o número atual de diferentes substrings, como recalcular essa contagem adicionando um caractere ao final.

Portanto, seja $k$ o número atual de diferentes substrings em $s$, e adicionamos o caractere $c$ ao final de $s$. Obviamente, algumas novas substrings terminadas em $c$ irão aparecer. Queremos contar essas novas substrings que não apareceram antes.

Pegamos a string $t = s + c$ e a invertemos. Agora, a tarefa é transformada em calcular quantos prefixos existem que não aparecem em nenhum outro lugar. Se calcularmos o valor máximo da função de prefixo $\pi_{\text{max}}$ da string revertida $t$, então, o prefixo mais longo que aparece em $s$ é $\pi_{\text{max}}$. Claramente também todos os prefixos de tamanho menor aparecem nele.

Portanto, o número de novas substrings que aparecem quando adicionamos um novo caractere $c$ é $|s| + 1 - \pi_{\text{max}}$.

Portanto, para cada caractere acrescentado, podemos calcular o número de novas substrings em $O(n)$ vezes, o que fornece uma complexidade de tempo de $O(n^2)$ no total.

É importante notar que também podemos calcular o número de diferentes substrings anexando os caracteres no início ou excluindo os caracteres do início ou do fim.

Comprimindo uma string

Dada uma string $s$ de tamanho $n$. Queremos encontrar a menor representação "comprimida" da string, ou seja, queremos encontrar 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$.

É claro que precisamos apenas encontrar o comprimento de $t$. Sabendo o comprimento, a resposta para o problema será o prefixo de $s$ com esse comprimento.

Vamos calcular a função de prefixo para $s$. Usando o último valor dele, definimos o valor $k = n - \pi[n - 1]$. Mostraremos que se $k$ divide $n$, então $k$ será a resposta; caso contrário, não haverá uma compactação efetiva e a resposta será $n$.

Deixe que $n$ seja divisível por $k$. Em seguida, a string pode ser particionada em blocos com o comprimento $k$. Por definição da função prefixo, o prefixo de comprimento $n - k$ será igual ao seu sufixo. Mas isso significa que o último bloco é igual ao bloco anterior. E o bloco anterior deve ser igual ao bloco anterior. E assim por diante. Como resultado, verifica-se que todos os blocos são iguais; portanto, podemos compactar a string $s$ no comprimento $k$.

É claro que ainda precisamos mostrar que esse valor é realmente otimizado. De fato, se houvesse uma compactação menor que $k$, a função de prefixo no final seria maior que $n - k$. Portanto, $k$ é realmente a resposta.

Agora vamos supor que $n$ não seja divisível por $k$. Mostramos que isso implica que o comprimento da resposta é $n$. Provamos isso por contradição. Supondo que exista uma resposta, e a compactação tenha comprimento $p$ ($p$ divide $n$). Então o último valor da função prefixo deve ser maior que $n - p$, ou seja, o sufixo cobrirá parcialmente o primeiro bloco. Agora considere o segundo bloco da string. Como o prefixo é igual ao sufixo, e o prefixo e o sufixo cobrem esse bloco e seu deslocamento um em relação ao outro $k$ não divide o comprimento do bloco $p$ (caso contrário, $k$ divide $n$), então todos os caracteres do bloco devem ser idênticos. Mas então, a string consistiria em apenas um caractere repetido várias vezes, portanto, podemos compactá-la para uma string de tamanho $1$, o que nos dá $k = 1$, e $k$ divide $n$. Contradição

$$\overbrace{s_0 ~ s_1 ~ s_2 ~ s_3}^p ~ \overbrace{s_4 ~ s_5 ~ s_6 ~ s_7}^p$$ $$s_0 ~ s_1 ~ s_2 ~ \underbrace{\overbrace{s_3 ~ s_4 ~ s_5 ~ s_6}^p ~ s_7}_{\pi[7] = 5}$$ $$s_4 = s_3, ~ s_5 = s_4, ~ s_6 = s_5, ~ s_7 = s_6 ~ \Rightarrow ~ s_0 = s_1 = s_2 = s_3$$

Construindo um autômato de acordo com a função de prefixo

Vamos retornar à concatenação para as duas strings através de um separador, ou seja, para as strings $s$ e $t$ calculamos a função de prefixo para a string $s + \# + t$. Obviamente, como $\#$ é um separador, o valor da função de prefixo nunca excederá $|s|$. Segue-se que é suficiente armazenar a string $s + \#$ e os valores da função de prefixo para ela, e podemos calcular a função de prefixo para todos os caracteres subsequentes rapidamente: $$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{precisa armazenar}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{nao precisa}}$$

De fato, nessa situação, conhecer o próximo caractere $c \in t$ e o valor da função de prefixo da posição anterior é informação suficiente para calcular o próximo valor da função de prefixo, sem usar caracteres anteriores da string $t$ e o valor do prefixo neles.

Em outras palavras, podemos construir um "automaton" (uma máquina de estados finitos): o estado nele é o valor atual da função de prefixo e a transição de um estado para outro será realizada através do próximo caractere.

Portanto, mesmo sem a string $t$, podemos construir uma tabela de transição $(\text{old}\_\pi, c) \rightarrow \text{new}\_\pi$ usando o mesmo algoritmo para calcular a tabela de transição:

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j])
                j = pi[j-1];
            if ('a' + c == s[j])
                j++;
            aut[i][c] = j;
        }
    }
}

No entanto, nesta forma, o algoritmo é executado em tempo $O(n^2 26)$ para as letras minúsculas do alfabeto. Observe que podemos aplicar programação dinâmica e usar as partes já calculadas da tabela. Sempre que vamos do valor $j$ para o valor $\pi[j-1]$, na verdade queremos dizer que a transição $(j, c)$ leva ao mesmo estado que a transição que $(\pi[j-1], c)$, e esta resposta já é calculada com precisão.

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i-1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

Como resultado, construímos o autômato em tempo $O(n 26)$.

Quando esse autômato é útil? Para começar, lembre-se de que usamos a função prefixo da string $s + \# + t$ e seus valores principalmente para uma única finalidade: encontrar todas as ocorrências da string $s$ na string $t$.

Portanto, o benefício mais óbvio desse autômato é a aceleração do cálculo da função de prefixo para a string $s + \# + t$. Ao criar o autômato para $s + \#$, não precisamos mais armazenar a string $s$ ou os valores do prefixo nela. Todas as transições já são computadas na tabela.

Mas há uma segunda aplicação, menos óbvia. Podemos usar o autômato quando a string $t$ é uma string enorme construída com algumas regras. Ela pode ser, por instância, uma das strings de Gray, ou uma string formada por uma combinação recursiva de várias strings curtas da entrada.

Para completar, resolveremos esse problema: dado um número $k \le 10^5$ e uma string $s$ de tamanho $\le 10^5$. Temos que calcular o número de ocorrências de $s$ na $k$-ésima string de Gray. Lembre-se de que as strings de Gray são definidas da seguinte maneira: $$\begin{align} g_1 &= "a"\\ g_2 &= "aba"\\ g_3 &= "abacaba"\\ g_4 &= "abacabadabacaba" \end{align}$$

Nesses casos, até construir a string $t$ será impossível, devido ao seu comprimento. A $k$-ésima string de Gray tem $2^k-1$ caracteres. No entanto, podemos calcular o valor da função de prefixo no final da string efetivamente, apenas conhecendo o valor da função de prefixo no início.

Além do próprio autômato, também calculamos os valores $G[i][j]$ - o valor do autômato após o processamento da string $g_i$ começando com o estado $j$. Além disso, calculamos os valores $K[i][j]$ - o número de ocorrências de $s$ em $g_i$, antes do processamento de $g_i$ começando com o estado $j$. $K[i][j]$ é o número de vezes que a função de prefixo assumiu o valor $|s|$ durante a execução das operações. A resposta para o problema será então $K[k][0]$.

Como podemos calcular esses valores? Primeiro, os valores básicos são $G[0][j] = j$ e $K[0][j] = 0$. E todos os valores subsequentes podem ser calculados a partir dos valores anteriores e usando o autômato. Para calcular o valor para alguns $i$ lembramos que a string $g_i$ consiste de $g_{i-1}$, o caractere $i$ do alfabeto, e $g_{i-1}$. Assim, o autômato entrará no estado: $$\text{mid} = \text{aut}[G[i-1][j]][i]$$ $$G[i][j] = G[i-1][\text{mid}]$$ Os valores para $K[i][j]$ também podem ser facilmente contados. $$K[i][j] = K[i-1][j] + (\text{mid} == |s|) + K[i-1][\text{mid}]$$

Assim, podemos resolver o problema das strings de Gray e, da mesma forma, também um grande número de outros problemas semelhantes. Por exemplo, o mesmo método também resolve o seguinte problema: recebemos uma string $s$ e alguns padrões $t_i$, cada um deles é especificado da seguinte maneira: é uma string de caracteres comuns e pode haver algumas inserções recursivas de strings anteriores da forma $t_k^{\text{cnt}}$, o que significa que neste local temos que inserir a string $t_k$ $\text{cnt}$ vezes. Um exemplo desses padrões: $$\begin{align} t_1 &= "abdeca"\\ t_2 &= "abc" + t_1^{30} + "abd"\\ t_3 &= t_2^{50} + t_1^{100}\\ t_4 &= t_2^{10} + t_3^{100} \end{align}$$

As substituições recursivas fazem com que os comprimentos das strings possam atingir a ordem de $100^{100}$.

Temos que encontrar o número de vezes que a string $s$ aparece em cada uma das strings.

O problema pode ser resolvido da mesma maneira, construindo o autômato da função de prefixo e, então, calculamos as transições para cada padrão usando os resultados anteriores.

Problemas