Explicación mínima del algoritmo de cambio cíclico

Question

Recientemente me he encontrado con este código sin ningún comentario. Encuentra un desplazamiento cíclico mínimo de la palabra (este código específicamente devuelve su índice en una cadena) y su algoritmo llamado Duval. Solo info que encontré describe el algoritmo en pocas palabras y tiene un código más limpio. Agradecería cualquier ayuda para entender este algoritmo. Siempre he encontrado que los algoritmos de texto son bastante difíciles y difíciles de entender.

int minLexCyc(const char *x) { 
    int i = 0, j = 1, k = 1, p = 1, a, b, l = strlen(x); 
    while(j+k <= (l<<1)) { 
     if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) { 
      i=j++; 
      k=p=1; 
     } else if (a<b) { 
      j+=k; 
      k=1; 
      p=j-i; 
     } else if (a==b && k!=p) { 
      k++; 
     } else { 
      j+=p; 
      k=1; 
     } 
    } 
    return i; 
} 

Answer 1

En primer lugar, creo que su código tiene un error. La última línea debe ser return p;. Creo que tengo el índice del desplazamiento cíclico lexicográficamente más pequeño, y p tiene el cambio más pequeño que coincide. También creo que su condición de detención es demasiado débil, es decir, usted está haciendo demasiadas comprobaciones después de haber encontrado una coincidencia, pero no estoy seguro exactamente de qué se trata.

Tenga en cuenta que i y j solo avanzan y que siempre es menor que j. Estamos buscando una cadena que coincida con la cadena que comienza en i, y estamos tratando de hacerla coincidir con una cadena que comienza en j. Hacemos esto comparando el carácter k'th de cada cuerda mientras aumentamos k (siempre que coincidan). Tenga en cuenta que solo cambiamos i si determinamos que la cadena que comienza en j es lexicográficamente menor que la cadena que comienza en j, y luego configuramos i a j y restablecemos k y p a sus valores iniciales.

no tengo tiempo para un análisis detallado, pero parece que

1. i = el inicio de la lexicográfico desplazamiento cíclico más pequeño
2. j = el inicio del desplazamiento cíclico estamos igualando en contra de la cambiar a partir de i
3. k = el carácter en las cadenas de i y j actualmente bajo consideración (el partido cadenas en las posiciones 1 a K-1
4. p = el desplazamiento cíclico bajo consideración (i creo p significa prefijo)

Editar Yendo más lejos

esta sección del código

if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) { 
     i=j++; 
     k=p=1; 

Mueve el inicio de la comparación con una cadena lexicográfico antes, cuando nos encontramos con uno y reinicializa todo lo demás.

esta sección

} else if (a<b) { 
     j+=k; 
     k=1; 
     p=j-i; 

es la parte difícil. Hemos encontrado un desajuste que es lexicográficamente posterior a nuestra cadena de referencia, por lo que saltamos hasta el final del texto coincidente hasta el momento, y comenzamos a buscar desde allí. También aumentamos p (nuestro paso). ¿Por qué podemos omitir todos los puntos de partida entre j y j + k? Esto se debe a que la cadena que comienza con i es lexicográficamente la más pequeña vista, y si la cola de la cadena j actual es mayor que la cadena en i, entonces cualquier sufijo de la cadena en j será mayor que la cadena en i.

Finalmente

} else if (a==b && k!=p) { 
     k++; 
    } else { 
     j+=p; 
     k=1; 

esto sólo comprueba que la cadena de longitud p a partir de i repeticiones.

** * hacer otras modificaciones Hacemos esto mediante el incremento de k hasta k == p, comprobando que el carácter k-ésima de la cadena a partir de i es igual a k-ésima del carácter de la cadena a partir de j. Una vez que k alcanza p, comenzamos a escanear de nuevo en la siguiente supuesta ocurrencia de la cadena.

Edite aún más para intentar responder a las preguntas de jethro.

Primero: el k != p en else if (a==b && k!=p) Aquí tenemos una coincidencia en que la k'th y todos los caracteres anteriores en las cadenas que comienzan en i y j son iguales. La variable p representa la longitud que creemos que es la cadena repetitiva. Cuando k != p, en realidad k < p, nos aseguramos de que los caracteres p en la cadena que comienza en i sean los mismos que los caracteres p de la cadena que comienza en j. Cuando k == p (la última cosa) deberíamos estar en un punto donde la cadena que comienza en j + k tiene el mismo aspecto que la cadena que comienza en j, entonces aumentamos j por p y ajustamos k a 1 y volvemos a comparar las dos cadenas.

Segundo: Sí, creo que está en lo cierto, debería regresar i. Estaba mal entendido el significado de "desplazamiento cíclico mínimo"

Answer 2

Puede ser el mismo que este algoritmo, cuya explicación se puede encontrar here:

int ComputeMaxSufPos(string w) 
{ 
    int i = 0, n = w.Length; 
    for (int j = 1; j < n; ++j) 
    { 
     int c, k = 0; 
     while ((c = w[(i + k) % n].CompareTo(w[(j + k) % n])) == 0 && k != n) 
     { k++; } 
     j += c > 0 ? k/(j - i) * (j - i) : k; 
     i = c > 0 ? j : i; 
    } 
    return i; 
}