Fatoração de Lyndon

Primeiro, vamos definir a noção de fatoração de Lyndon.

Uma string é chamada simples (ou uma palavra de Lyndon), se for estritamente menor que qualquer um de seus próprios sufixos. Exemplos: $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$. Pode-se mostrar que uma string é simples, se e somente se for estritamente menor que todas as suas mudanças cíclicas.

A seguir, seja uma string $s$. A fatoração Lyndon da string $s$ é uma fatoração $s = w_1 w_2 \dots w_k$, onde todas strings $w_i$ são simples, e estão em ordem não crescente $w_1 \ge w_2 \ge \dots \ge w_k$.

Pode ser mostrado que, para qualquer string, existe uma fatoração e ela será única.

Algoritmo de Duval

O algoritmo Duval constrói a fatoração de Lyndon em tempo $O(n)$ usando $O(1)$ de memória adicional.

Primeiro, vamos introduzir outra noção: uma string $t$ é definida como pré-simples, se tiver a forma $t = w w \dots w \overline{w}$, onde $w$ é uma string simples e $\overline{w}$ é um prefixo de $w$ (possivelmente vazio). Uma string simples também é pré-simples.

O algoritmo de Duval é guloso(greedy). A qualquer momento durante sua execução, a string $s$ será dividida em três strings $s = s_1 s_2 s_3$, onde a fatoração de Lyndon para $s_1$ já foi encontrada e finalizada, a string $s_2$ é pré-simples (e sabemos o comprimento da string simples) e $s_3$ ainda está praticamente intocada. Em cada iteração, o algoritmo Duval pega o primeiro caractere da string $s_3$ e tenta anexá-lo à string $s_2$. Como $s_2$ não é mais pré-simples, a fatoração de Lyndon para uma parte de $s_2$ se torna conhecida e essa parte vai para $s_1$.

Vamos descrever o algoritmo em mais detalhes. O ponteiro $i$ sempre apontará para o início da string $s_2$. O loop externo será executado contanto que $i < n$. Dentro do loop, usamos dois ponteiros adicionais, $j$ que aponta para o início de $s_3$, e $k$ que aponta para o caractere atual com o qual estamos comparando atualmente. Queremos adicionar o caractere $s[j]$ na string $s_2$, o que requer uma comparação com o caractere $s[k]$. Pode haver três casos diferentes:

Implementação

Aqui apresentamos a implementação do algoritmo de Duval, que retornará a fatoração de Lyndon desejada de uma determinada string $s$.

vector<string> duval(string const& s) {
    int n = s.size();
    int i = 0;
    vector<string> factorization;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k) {
            factorization.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return factorization;
}

Complexidade

Vamos estimar o tempo de execução desse algoritmo.

O loop while externo não excede $n$ iterações, pois no final de cada iteração $i$ aumenta. Além disso, o segundo loop while interno é executado em $O(n)$, uma vez que ele apenas gera a fatoração final.

Então, estamos interessados ​​apenas no primeiro while interno. Quantas iterações são executadas no pior caso? É fácil ver que as palavras simples que identificamos em cada iteração do loop externo são mais longas que o restante que comparamos adicionalmente. Portanto, também a soma dos restantes será menor que $n$, o que significa que apenas realizamos no máximo $O(n)$ iterações do primeiro loop while interno. De fato, o número total de comparações de caracteres não excederá $4n - 3$.

Encontrar a menor mudança cíclica

Seja uma string $s$. Construímos a fatoração de Lyndon para a string $s + s$ (em tempo $O(n)$). Procuraremos uma string simples na fatoração, que começa em uma posição menor que $n$ (ou seja, começa na primeira instância de $s$), e termina em uma posição maior ou igual a $n$ (ou seja, na segunda instância de $s$). É afirmado que a posição do início desta string simples será o início da menor mudança cíclico desejada. Isso pode ser facilmente verificado usando a definição da decomposição de Lyndon.

O início do bloco simples pode ser encontrado facilmente - lembre do ponteiro $i$ no início de cada iteração do loop externo, que indicava o início da atual string pré-simples.

Portanto, obtemos a seguinte implementação:

string min_cyclic_string(string s) {
    s += s;
    int n = s.size();
    int i = 0, ans = 0;
    while (i < n / 2) {
        ans = i;
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k)
            i += j - k;
    }
    return s.substr(ans, n / 2);
}

Problemas