En informática , la rotación de cadena lexicográficamente mínima o la subcadena lexicográficamente 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áfica mínima de "bbaaccaadd" sería "aaccaaddbb". Es posible que una cadena tenga múltiples rotaciones lexicográficamente mínimas, pero para la mayoría de las aplicaciones esto no importa ya que las rotaciones deben ser equivalentes. Encontrar la rotación lexicográficamente mínima es útil como forma de normalizar cadenas. Si las cadenas representan estructuras potencialmente isomórficas , como gráficos , la normalización de esta manera permite una verificación de igualdad simple. [1] Un truco de implementación común cuando se trata de cadenas circulares es concatenar la cadena consigo misma en lugar de tener que realizar aritmética modular en los índices de la cadena.
El algoritmo ingenuo para encontrar la rotación lexicográficamente mínima de una cadena es iterar a través de rotaciones sucesivas mientras se realiza un seguimiento de la rotación lexicográficamente mínima encontrada. Si la cadena tiene una longitud n , este algoritmo se ejecuta en tiempo O ( n 2 ) en el peor de los casos.
Booth (1980) propuso un algoritmo eficiente. [2] El algoritmo utiliza una función de preprocesamiento modificada del algoritmo de búsqueda de cadenas Knuth-Morris-Pratt . La función de falla para la cadena se calcula normalmente, pero la cadena se gira durante el cálculo, por lo que algunos índices deben calcularse más de una vez a medida que se ajustan. Una vez que todos los índices de la función de falla se han calculado exitosamente sin que la cadena vuelva a girar, se sabe que se encuentra la rotación lexicográfica mínima y se devuelve su índice inicial. La exactitud del algoritmo es algo difícil de entender, pero es fácil de implementar.
def less_rotation ( s : str ) -> int : """Algoritmo lexicográficamente mínimo de rotación de cadenas de Booth.""" n = len ( s ) f = [ - 1 ] * ( 2 * n ) k = 0 para j en el rango ( 1 , 2 * n ): i = f [ j - k - 1 ] mientras i != - 1 y s [ j % n ] != s [( k + i + 1 ) % n ]: si s [ j % n ] < s [( k + i + 1 ) % n ]: k = j - i - 1 i = f [ i ] si i == - 1 y s [ j % n ] != s [( k + i + 1 ) % n ]: si s [ j % n ] < s [( k + i + 1 ) % n ]: k = j f [ j - k ] = - 1 más : f [ j - k ] = i + 1 vuelta k Es interesante que eliminar todas las líneas de código que modifican el valor de k da como resultado la función de preprocesamiento original de Knuth-Morris-Pratt, ya que k (que representa la rotación) permanecerá cero. El algoritmo de Booth se ejecuta en el tiempo, donde n es la longitud de la cadena. El algoritmo realiza como máximo comparaciones en el peor de los casos y requiere una memoria auxiliar de longitud n para contener la tabla de funciones de falla.
Shiloach (1981) [3] 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 consistir en q subcadenas iguales de longitud . El algoritmo sólo requiere comparaciones y espacio constante en el peor de los casos.
El algoritmo se divide en dos fases. La primera fase es un tamiz rápido que descarta índices que obviamente no son lugares de partida para la rotación lexicográficamente mínima. La segunda fase encuentra entonces el índice de inicio de rotación lexicográficamente mínimo a partir de los índices que quedan.
Duval (1983) [4] 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.
Shiloach (1979) [5] propuso un algoritmo para comparar eficientemente la igualdad de dos cadenas circulares sin un requisito de normalización. Una aplicación adicional que surge del algoritmo es la generación rápida de determinadas estructuras químicas sin repeticiones.
