Menor rotação lexicográfica de uma string usando matrizes de sufixo em O (n)

Vou citar o problema do ACM 2003:

Considere uma sequência de comprimento n (1 <= n <= 100000). Determine sua rotação lexicográfica mínima. Por exemplo, as rotações da string "alabala" são:

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

e o menor deles é "aalabal".

Quanto à solução - eu sei que preciso construir uma matriz de sufixos - e digamos que eu possa fazer isso em O (n). Minha pergunta ainda é: como posso encontrar a menor rotação em O (n)? (n = comprimento de uma string)

Estou muito interessado neste problema e ainda assim não entendo a solução. Estou mais interessado no conceito e em como resolver o problema e não na implementação concreta.

Nota: rotação mínima significa na mesma ordem que em um dicionário de inglês - "dwor" está antes de "word" porque d está antes de w.

EDIT: construção de matriz de sufixo leva O (N)

ÚLTIMA EDIÇÃO: Acho que encontrei uma solução !!! E se eu apenas fundisse duas strings? Então, se a string é "alabala", a nova string seria "alabalaalabala" e agora eu apenas construí uma matriz de sufixos disso (em O (2n) = O (n)) e recebo o primeiro sufixo? Eu acho que isso pode estar certo. O que você acha? Obrigado!

Um truque simples para construir todas as rotações de uma sequência de comprimento N é concatenar a sequência consigo mesma.

Então, toda substring de comprimento N dessa cadeia de comprimento 2N é uma rotação da cadeia original.

A localização da subcadeia "lexicograficamente mínima" é feita com a construção da árvore O (N).

Tenho certeza de que as informações contidas em uma matriz de sufixos não são suficientes para ajudá-lo a chegar a O (n), mas, no máximo, podem ajudá-lo a O (n log n). Considere esta família de sufixos:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Você constrói o próximo sufixo usando o sufixo anterior (digamos aba), adicionando o próximo caractere ainda não usado e adicionando o sufixo anterior novamente (então aba -> aba c aba).

Agora considere essas cadeias (o espaço é adicionado para dar ênfase, mas não faz parte da cadeia):

ad abacaba
bd abacaba
cd abacaba

Para essas três strings, o início da matriz de sufixos será parecido com o seguinte:

a
aba
abacaba
(other suffixes)

Parece familiar? Naturalmente, essas strings são personalizadas para criar essa matriz de sufixos. Agora, dependendo da letra inicial (a, b ou c), o índice 'correto' (a solução para o seu problema) é o primeiro, o segundo ou o terceiro sufixo da lista acima.

A escolha da primeira letra dificilmente afeta a matriz de sufixos; em particular, isso não afeta a ordem dos três primeiros sufixos na matriz de sufixos. Isso significa que temos log n strings para as quais a matriz de sufixos é extremamente semelhante, mas o índice 'correto' é muito diferente.

Embora eu não tenha provas concretas, isso sugere fortemente que você não tem escolha a não ser comparar as rotações correspondentes a esses três primeiros índices na matriz para a sua ordenação lexicográfica, o que, por sua vez, significa que você precisará de pelo menos O (n log n) tempo para isso (como o número de primeiros caracteres alternativos - no nosso caso 3 - é log n, e comparar duas cadeias leva tempo O (n)).

Isso não descarta a possibilidade de um algoritmo O (n). Apenas tenho dúvidas de que uma matriz de sufixos o ajude a atingir esse tempo de execução.

A menor rotação é aquela que começa com parte do sufixo da matriz de sufixos. Sufixos são ordenados lexicograficamente. Isso fornece um grande impulso:

• você sabe que depois de obter k que a rotação iniciada com o sufixo k é menor que a rotação iniciada com o sufixo k +1, você está pronto (a partir da primeira);
• você pode fazer a comparação de "rotação iniciada com o sufixo k é menor que rotação iniciada com o sufixo k +1" em O (1) comparando comprimentos de sufixos e, opcionalmente, comparando um caractere com outro.

EDIT: "um caractere com outro caractere" nem sempre pode ser assim, pode ser mais de um caractere, mas no geral, você não examina mais de n caracteres durante todo o processo de pesquisa, portanto é O (n).

Prova curta: você examina os caracteres apenas quando o sufixo k +1 é maior que o sufixo k e para e encontra a solução se o sufixo k +1 é menor que o sufixo k (então você sabe que o sufixo k é o que você procurava). Portanto, você só examina os caracteres enquanto está em seqüência crescente (longitudinal) de sufixos. Como você examina apenas caracteres em excesso, não pode examinar mais de n caracteres.

EDIT2: Este algoritmo baseia-se no fato de que "se houver dois sufixos vizinhos na matriz de sufixos e o anterior for menor que o subsequente, o anterior será o prefixo do subsequente". Se isso não for verdade, desculpe.

EDIT3: Não, não é válido. "abaaa" possui a tabela de sufixos "a", "aa", "aaa", "abaaa", "baaa". Mas talvez essa linha de pensamento possa levar à solução, apenas mais alguns detalhes devem ser mais sofisticados. A questão principal é se é possível, de alguma maneira, fazer a comparação mencionada examinando menos caracteres; portanto, é O (n) totalmente, o que, de alguma forma, acredito que seja possível. Eu simplesmente não posso dizer como, agora.

Problema:

A substring Lexicographically menos circular é o problema de encontrar a rotação de uma corda que possui a ordem lexicográfica mais baixa de todas essas rotações. Por exemplo, a rotação lexicograficamente mínima de "bbaaccaadd" seria "aaccaaddbb".

Solução:

O algoritmo AO (n) time foi proposto por Jean Pierre Duval (1983).

Dados dois índices ie j, o algoritmo de Duval compara segmentos de cadeia de comprimento j - icomeçando em ie j(chamado de "duelo" ). Se index + j - ifor maior que o comprimento da sequência, o segmento é formado ao redor.

Por exemplo, considere s = "baabbaba", i = 5 ej = 7. Como j - i = 2, o primeiro segmento começando em i = 5 é "ab". O segundo segmento começando em j = 7 é construído ao redor e também é "ab". Se as cadeias são lexicograficamente iguais, como no exemplo acima, escolhemos a que começa em i como a vencedora, que é i = 5.

O processo acima foi repetido até termos um único vencedor. Se a sequência de entrada tiver um comprimento ímpar, o último caractere vence sem uma comparação na primeira iteração.

Complexidade do tempo:

A primeira iteração compara n seqüências cada de comprimento 1 (comparações n / 2), a segunda iteração pode comparar n / 2 seqüências de comprimento 2 (comparações n / 2) e assim por diante, até que a i-ésima iteração compara duas seqüências de caracteres de comprimento n / 2 (comparações n / 2). Como o número de vencedores é dividido pela metade a cada vez, a altura da árvore de recursão é log (n), fornecendo assim um algoritmo O (n log (n)). Para n pequeno, isso é aproximadamente O (n).

A complexidade do espaço também é O (n), pois na primeira iteração, temos que armazenar n / 2 vencedores, segunda iteração n / 4 vencedores e assim por diante. (A Wikipedia afirma que esse algoritmo usa espaço constante, não entendo como).

Aqui está uma implementação do Scala; fique à vontade para converter para sua linguagem de programação favorita.

def lexicographicallyMinRotation(s: String): String = {
 @tailrec
 def duel(winners: Seq[Int]): String = {
   if (winners.size == 1) s"${s.slice(winners.head, s.length)}${s.take(winners.head)}"
   else {
     val newWinners: Seq[Int] = winners
       .sliding(2, 2)
       .map {
         case Seq(x, y) =>
           val range = y - x
           Seq(x, y)
             .map { i =>
               val segment = if (s.isDefinedAt(i + range - 1)) s.slice(i, i + range)
               else s"${s.slice(i, s.length)}${s.take(s.length - i)}"
               (i, segment)
             }
             .reduce((a, b) => if (a._2 <= b._2) a else b)
             ._1
         case xs => xs.head
       }
       .toSeq
     duel(newWinners)
   }
 }

 duel(s.indices)
}

Não vejo nada melhor que O (N²).

Se você tiver uma lista de N números inteiros, poderá escolher a menor das comparações de O (N).

Aqui você tem uma lista de N strings de tamanho N (construí-las não custa nada, uma string é totalmente determinada pelo seu índice inicial). Você pode escolher as menores comparações de O (N). Mas cada comparação é O (N) operações básicas. Então a complexidade é O (N²).