Rotación de cadena lexicográficamente mínima

^{El algoritmo ingenuo para encontrar la rotación lexicográficamente mínima de una cadena consiste en iterar a través de rotaciones sucesivas ,} registrando la rotación lexicográficamente mínima encontrada. Si la cadena tiene una longitud n , este algoritmo se ejecuta en tiempo O ( n² ) en el peor de los casos.

Booth (1980) propuso un algoritmo eficiente. ^{[ 3 ]} El algoritmo utiliza una función de preprocesamiento modificada del algoritmo de búsqueda de cadenas de Knuth-Morris-Pratt . La función de fallo para la cadena se calcula de forma habitual, pero la cadena se rota durante el cálculo, por lo que algunos índices deben calcularse más de una vez al repetirse. Una vez que todos los índices de la función de fallo se han calculado correctamente sin que la cadena vuelva a rotar, se sabe que se ha encontrado la rotación lexicográfica mínima y se devuelve su índice inicial. La corrección del algoritmo es algo difícil de comprender, pero es fácil de implementar.

def least_rotation ( s : str ) -> int : """Algoritmo de rotación de cadenas lexicográficamente mínimo de Booth.""" n = len ( s ) f = [ - 1 ] * ( 2 * n ) k = 0 for j in range ( 1 , 2 * n ): i = f [ j - k - 1 ] while i != - 1 and s [ j % n ] != s [( k + i + 1 ) % n ]: if s [ j % n ] < s [( k + i + 1 ) % n ]: k = j - i - 1 i = f [ i ] if i == - 1 and s [ j % n ] != s [( k + i + 1 ) % n ]: if s [ j % n ] < s [( k + i + 1 ) % n ] ]: k = j f [ j - k ] = - 1 else : f [ j - k ] = i + 1 return k

Resulta interesante observar que al eliminar todas las líneas de código que modifican el valor de k se obtiene la función de preprocesamiento original de Knuth-Morris-Pratt, ya que k (que representa la rotación) permanecerá en cero. El algoritmo de Booth se ejecuta en ⁠${\displaystyle O(n)}$tiempo , donde n es la longitud de la cadena. El algoritmo realiza como máximo${\displaystyle 3n}$comparaciones en el peor de los casos, y requiere memoria auxiliar de longitud n para almacenar la tabla de funciones de fallo.

Shiloach (1981) ^{[ 4 ]} propuso un algoritmo que mejoraba el resultado de Booth en términos de rendimiento. Se observó que si hay q rotaciones lexicográficamente mínimas equivalentes de una cadena de longitud n , entonces la cadena debe constar de q subcadenas iguales de longitud n.${\displaystyle d=n/q}$⁠ . El algoritmo solo requiere ⁠${\displaystyle n+d/2}$comparaciones y espacio constante en el peor de los casos.

El algoritmo se divide en dos fases. La primera fase consiste en un filtrado rápido que descarta los índices que obviamente no son puntos de partida para la rotación lexicográficamente mínima. La segunda fase, a partir de los índices restantes, encuentra el índice de inicio de la rotación lexicográficamente mínima.

Duval (1983) ^{[ 5 ]} propuso un algoritmo eficiente que implica la factorización de la cadena en sus palabras Lyndon componentes , que se ejecuta en tiempo lineal con un requisito de memoria constante.