Encontrando repetições

Dada uma string $s$ de tamanho $n$.

Uma repetição é duas ocorrências de uma string em uma linha. Em outras palavras, uma repetição pode ser descrita por um par de índices $i < j$ de modo que a substring $s[i \dots j]$ consista em duas strings idênticas escritas uma após a outra.

O desafio é encontrar todas as repetições em uma determinada string $s$. Ou uma tarefa simplificada: encontre qualquer repetição ou a repetição mais longa.

O algoritmo descrito aqui foi publicado em 1982 por Main e Lorentz.

Exemplo

Considere as repetições na seguinte string: $$acababaee$$ A sequência contém as três repetições a seguir:

Outro exemplo: $$abaaba$$ Aqui existem apenas duas repetições

Número de repetições

Em geral, pode haver até $O(n^2)$ repetições em uma string de tamanho $n$. Um exemplo óbvio é uma string que consiste em $n$ vezes a mesma letra; nesse caso, qualquer substring de comprimento par é uma repetição. Em geral, qualquer sequência periódica com um período curto conterá muitas repetições.

Por outro lado, esse fato não impede o cálculo do número de repetições em tempo $O(n \log n)$, porque o algoritmo pode fornecer as repetições em diferentes formas e em grupos de várias peças ao mesmo tempo.

Existe até o conceito, que descreve grupos de substrings periódicos com tuplas de tamanho quatro. Provou-se que o número de tais grupos é no máximo linear em relação ao comprimento da string.

Além disso, aqui estão alguns resultados mais interessantes relacionados ao número de repetições:

Algoritmo de Main-Lorentz

A idéia por trás do algoritmo Main-Lorentz é dividir e conquistar.

Ele divide a string inicial em duas metades e calcula o número de repetições que se encontram completamente em cada metade por duas chamadas recursivas. Depois vem a parte difícil. O algoritmo encontra todas as repetições começando na primeira metade e terminando na segunda metade (que chamaremos de repetições cruzadas). Esta é a parte essencial do algoritmo Main-Lorentz, e vamos discuti-lo em detalhes aqui.

A complexidade dos algoritmos de dividir e conquistar é bem pesquisada. O teorema principal diz que acabaremos com um algoritmo $O(n \log n)$, se pudermos calcular as repetições de cruzamento em $O(n)$.

Procurar por repetições cruzadas

Então, queremos encontrar todas essas repetições que começam na primeira metade da string, vamos chamar de $u$, e terminam na segunda metade, vamos chamar de $v$: $$s = u + v$$ Seus tamanhos são aproximadamente iguais ao comprimento de $s$ dividido por dois.

Considere uma repetição arbitrária e observe o caractere do meio (mais precisamente o primeiro caractere da segunda metade da repetição). Ou seja, se a repetição for uma substring $s[i \dots j]$, o caractere do meio será $(i + j + 1) / 2$.

Chamamos uma repetição esquerda ou direita dependendo de qual string esse caractere está localizado - na string $u$ ou na string $v$. Em outras palavras, uma string é chamada esquerda, se a maioria estiver em $u$, caso contrário, a chamaremos direita.

Agora discutiremos como encontrar todas repetições a esquerda. Encontrar todas as repetições a direita pode ser feito da mesma maneira.

Vamos denotar o tamanho da repetição esquerda em $2l$ (ou seja, cada metade da repetição tem comprimento $l$). Considere o primeiro caractere da repetição que fica na string $v$ (na posição $|u|$ na string $s$). Ele coincide com o caractere $l$ posições antes dele, vamos denotar essa posição $cntr$.

Fixaremos esta posição $cntr$, e procuraremos todas as repetições nessa posição $cntr$.

Por exemplo: $$c ~ \underset{cntr}{a} ~ c ~ | ~ a ~ d ~ a$$ As linhas verticais dividem as duas metades. Aqui fixamos a posição $cntr = 1$, e, nessa posição, encontramos a repetição $caca$.

É claro que, se fixarmos a posição $cntr$, simultaneamente fixaremos o tamanho das repetições possíveis: $l = |u| - cntr$. Depois que soubermos encontrar essas repetições, iteraremos sobre todos os valores possíveis para $cntr$ de $0$ até $|u|-1$, e encontraremos todas as repetições cruzadas à esquerda de tamanho $l = |u|,~ |u|-1,~ \dots, 1$.

Critério para repetições cruzadas à esquerda

Agora, como podemos encontrar todas essas repetições para um $cntr$ fixo? Lembre-se de que ainda pode haver várias repetições desse tipo.

Vejamos novamente uma visualização, desta vez para a repetição $abcabc$: $$\overbrace{a}^{l_1} ~ \overbrace{\underset{cntr}{b} ~ c}^{l_2} ~ \overbrace{a}^{l_1} ~ | ~ \overbrace{b ~ c}^{l_2}$$ Aqui denotamos os comprimentos das duas partes da repetição com $l_1$ e $l_2$: $l_1$ é o comprimento da repetição até a posição $cntr-1$, e $l_2$ é o comprimento da repetição de $cntr$ até o final da metade da repetição. Temos $2l = l_1 + l_2 + l_1 + l_2$ como o comprimento total da repetição.

Vamos gerar condições suficientes para essa repetição na posição $cntr$ de tamanho $2l = 2(l_1 + l_2) = 2(|u| - cntr)$:

Para resumir:

Portanto, a única parte restante é como podemos calcular os valores $k_1$ e $k_2$ rapidamente para cada posição $cntr$. Felizmente, podemos calculá-los em $O(1)$ usando a função Z:

Portanto, isso é suficiente para encontrar todas as repetições cruzadas à esquerda.

Repetições cruzadas à direita

Para calcular as repetições cruzadas à direita, agimos da mesma forma: definimos o centro $cntr$ como o caractere correspondente ao último caractere na string $u$.

Então o comprimento $k_1$ será definido como o maior número de caracteres antes da posição $cntr$ que coincida com os últimos caracteres da string $u$. E o comprimento $k_2$ será definido como o maior número de caracteres começando em $cntr + 1$ que coincide com os caracteres da string $v$.

Assim, podemos encontrar os valores $k_1$ e $k_2$ calculando a função Z para as strings $\overline{u} + \# + \overline{v}$ e $v$.

Depois disso, podemos encontrar as repetições observando todas as posições $cntr$, e usar o mesmo critério que tínhamos para repetições cruzadas à esquerda.

Implementação

A implementação do algoritmo Main-Lorentz encontra todas as repetições na forma de tuplas: $(cntr,~ l,~ k_1,~ k_2)$ em tempo $O(n \log n)$. Se você deseja apenas encontrar o número de repetições em uma string, ou apenas a maior repetição em uma string, essas informações são suficientes e o tempo de execução ainda será $O(n \log n)$.

Observe que se você deseja expandir essas tuplas para obter a posição inicial e final de cada repetição, o tempo de execução será de $O(n^2)$ (podem existir $O(n^2)$ repetições). Nesta implementação, faremos isso e armazenaremos toda a repetição encontrada em um vetor de pares de índices inicial e final.

vector<int> z_function(string const& s) {
    int n = s.size();
    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;
}

int get_z(vector<int> const& z, int i) {
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}

vector<pair<int, int>> repetitions;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
        if (left && l1 == l) break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2*l - 1);
    }
}

void find_repetitions(string s, int shift = 0) {
    int n = s.size();
    if (n == 1)
        return;

    int nu = n / 2;
    int nv = n - nu;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++) {
        int l, k1, k2;
        if (cntr < nu) {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}