La rotación lexicográfica más pequeña de una cadena utilizando matrices de sufijos en O (n)

Citaré el problema de ACM 2003:

Considere una cadena de longitud n (1 <= n <= 100000). Determinar su rotación lexicográfica mínima. Por ejemplo, las rotaciones de la cadena "alabala" son:

alabala

labalaa

abalaal

balaala

alaalab

laalaba

alabal

y el más pequeño de ellos es "aalabal".

En cuanto a la solución, sé que necesito construir una matriz de sufijos , y digamos que puedo hacerlo en O (n). Mi pregunta aún es, ¿cómo puedo encontrar la rotación más pequeña en O (n)? (n = longitud de una cadena)

Estoy muy interesado en este problema y aún así no consigo la solución. Estoy más interesado en el concepto y en cómo resolver el problema y no en la implementación concreta.

Nota: rotación mínima significa en el mismo orden que en un diccionario de inglés: "dwor" está antes de "word" porque d está antes de w.

EDITAR: la construcción de matriz de sufijo toma O (N)

ÚLTIMA EDICIÓN: ¡Creo que encontré una solución! ¿Qué pasa si acabo de fusionar dos cadenas? Entonces, si la cadena es "alabala", la nueva cadena me "alabalaalabala" y ahora simplemente construiría una matriz de sufijos de esto (en O (2n) = O (n)) y obtendría el primer sufijo. Supongo que esto puede ser correcto. ¿Qué piensas? ¡Gracias!

Un truco simple para construir todas las rotaciones de una cadena de longitud N es concatenar la cadena consigo misma.

Entonces, cada subcadena de longitud N de esta cadena de longitud 2N es una rotación de la cadena original.

La localización de la subcadena "lexicográficamente mínima" se realiza con la construcción de su árbol O (N).

Estoy bastante seguro de que la información contenida en una matriz de sufijos no es suficiente para ayudarlo a llegar a O (n), pero a lo sumo puede ayudarlo a O (n log n). Considere esta familia de sufijos:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Usted construye el siguiente sufijo tomando el sufijo anterior (digamos aba), agregando el siguiente carácter que aún no se usó y luego agregando el sufijo anterior nuevamente (entonces aba -> aba c aba).

Ahora considere estas cadenas (el espacio se agrega para enfatizar, pero no es parte de la cadena):

ad abacaba
bd abacaba
cd abacaba

Para estas tres cadenas, el inicio de la matriz de sufijos se verá así:

a
aba
abacaba
(other suffixes)

¿Luce familiar? Estas cadenas, por supuesto, están diseñadas para crear esta matriz de sufijos. Ahora, dependiendo de la letra inicial (a, b o c), el índice 'correcto' (la solución a su problema) es el primer, el segundo o el tercer sufijo en la lista anterior.

La elección de la primera letra apenas afecta la matriz de sufijos; en particular, no afecta el orden de los primeros tres sufijos en la matriz de sufijos. Esto significa que tenemos cadenas log n para las cuales la matriz de sufijos es extremadamente similar pero el índice 'correcto' es muy diferente.

Aunque no tengo pruebas sólidas, esto me sugiere que no tiene más remedio que comparar las rotaciones correspondientes a estos tres primeros índices en la matriz para su ordenación lexicográfica, lo que a su vez significa que necesitará al menos O (n log n) tiempo para esto (ya que el número de primeros caracteres alternativos, en nuestro caso 3, es log n, y comparar dos cadenas lleva tiempo O (n)).

Esto no descarta la posibilidad de un algoritmo O (n). Simplemente tengo dudas de que una matriz de sufijos lo ayude a lograr este tiempo de ejecución.

La rotación más pequeña es la que comienza con algunos de los sufijos de la matriz de sufijos. Los sufijos están ordenados lexicográficamente. Esto te da un gran comienzo:

• usted sabe que una vez que obtiene tal k que la rotación que comienza con el sufijo k es menor que la rotación que comienza con el sufijo k +1, ya está (comenzando desde el primero);
• puede hacer la comparación de "la rotación que comienza con el sufijo k es menor que la rotación que comienza con el sufijo k +1" en O (1) comparando longitudes de sufijos y, opcionalmente, comparando un carácter con otro carácter.

EDITAR: "un carácter con otro carácter" puede no ser siempre así, puede ser más de un carácter, pero en general, no examina más de n caracteres durante todo el proceso de búsqueda, por lo que es O (n).

Prueba corta: solo examina los caracteres cuando el sufijo k +1 es más largo que el sufijo k , y se detiene y encuentra su solución si el sufijo k +1 es más corto que el sufijo k (entonces sabe que el sufijo k es el que buscaba). Por lo tanto, solo examina los caracteres mientras está en secuencia ascendente (en cuanto a la longitud) de sufijos. Como solo examina los caracteres en exceso, no puede examinar más de n caracteres.

EDIT2: Este algoritmo se basa en el hecho de que "si hay dos sufijos vecinos en la matriz de sufijos y el anterior es más corto que el subsiguiente, el anterior es el prefijo del subsiguiente". Si esto no es cierto, lo siento.

EDITAR3: No, no se cumple. "abaaa" tiene la tabla de sufijos "a", "aa", "aaa", "abaaa", "baaa". Pero tal vez esta línea de pensamiento pueda conducir finalmente a la solución, solo algunos detalles más deben ser más sofisticados. La pregunta principal es si es posible de alguna manera hacer la comparación mencionada al examinar menos caracteres, por lo que es O (n) totalmente, lo que de alguna manera creo que es posible. No puedo decir cómo, ahora.

Problema:

Lexicográficamente, la subcadena menos circular es el problema de encontrar la rotación de una cadena que posee el orden lexicográfico más bajo de todas esas rotaciones. Por ejemplo, la rotación lexicográficamente mínima de "bbaaccaadd" sería "aaccaaddbb".

Solución:

El algoritmo de tiempo AO (n) fue propuesto por Jean Pierre Duval (1983).

Dados dos índices iy j, el algoritmo de Duval compara segmentos de longitud de cadena que j - icomienzan en iy j(llamado "duelo" ). Si index + j - ies mayor que la longitud de la cadena, el segmento se forma envolviendo.

Por ejemplo, considere s = "baabbaba", i = 5 y j = 7. Como j - i = 2, el primer segmento que comienza en i = 5 es "ab". El segundo segmento que comienza en j = 7 se construye envolviendo y también es "ab". Si las cadenas son lexicográficamente iguales, como en el ejemplo anterior, elegimos el que comienza en i como ganador, que es i = 5.

El proceso anterior se repite hasta que tengamos un único ganador. Si la cadena de entrada es de longitud impar, el último carácter gana sin comparación en la primera iteración.

Complejidad del tiempo:

La primera iteración compara n cadenas de longitud 1 (n / 2 comparaciones), la segunda iteración puede comparar n / 2 cadenas de longitud 2 (n / 2 comparaciones), y así sucesivamente, hasta que la i-ésima iteración compare 2 cadenas de longitud n / 2 (n / 2 comparaciones). Dado que el número de ganadores se reduce a la mitad cada vez, la altura del árbol de recursión es log (n), lo que nos da un algoritmo O (n log (n)). Para n pequeña, esto es aproximadamente O (n).

La complejidad del espacio también es O (n), ya que en la primera iteración, tenemos que almacenar n / 2 ganadores, la segunda iteración n / 4 ganadores, y así sucesivamente. (Wikipedia afirma que este algoritmo usa espacio constante, no entiendo cómo).

Aquí hay una implementación de Scala; siéntase libre de convertir a su lenguaje de programación favorito.

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)
}

No veo nada mejor que O (N²).

Si tiene una lista de N enteros, puede elegir el más pequeño en las comparaciones O (N).

Aquí tiene una lista de N cadenas de tamaño N (construirlas no cuesta nada, una cadena está completamente determinada por su índice inicial). Puede elegir el más pequeño en las comparaciones O (N). Pero cada comparación es O (N) operaciones básicas. Entonces la complejidad es O (N²).