Explication de l'algorithme de décalage cyclique minimal

Question

Je me suis récemment heurté à ce code sans aucun commentaire. Il trouve un décalage cyclique minimal du mot (ce code renvoie spécifiquement son index en chaîne) et son algorithme Duval appelé. Seulement info J'ai trouvé décrit l'algorithme en quelques mots et a un code plus propre. J'apprécierais toute aide dans la compréhension de cet algorithme. J'ai toujours trouvé des algorithmes de texte assez compliqués et plutôt difficiles à comprendre.

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

D'abord, je crois que votre code contient un bogue. La dernière ligne doit être return p;. Je crois que je détiens l'indice du décalage cyclique lexicographiquement le plus petit et p le plus petit décalage correspondant. Je pense aussi que votre condition d'arrêt est trop faible, c'est-à-dire que vous faites trop de vérifications après avoir trouvé une correspondance, mais je ne suis pas sûr de ce que cela devrait être. Notez que i et j avancent seulement et que i est toujours inférieur à j. Nous recherchons une chaîne qui correspond à la chaîne commençant par i, et nous essayons de la faire correspondre avec une chaîne qui commence à j. Nous faisons cela en comparant le caractère k'th de chaque chaîne tout en augmentant k (tant qu'ils correspondent). Notez que nous ne changeons que i si nous déterminons que la chaîne commençant par j est lexicographiquement inférieure à la chaîne commençant par j, puis nous définissons i et j et réinitialisons k et p à leurs valeurs initiales.

Je n'ai pas le temps pour une analyse détaillée, mais il semble que

1. i = le début du décalage cyclique plus petit lexicographique
2. j = le début du décalage cyclique nous correspondant contre la déplacer à partir de i
3. k = le caractère dans une chaîne i et j actuellement à l'étude (les chaînes correspondent aux positions 1 à k-1
4. p = le décalage cyclique considéré (i crois p représente préfixe)

Modifier Allant plus loin

cette section de code

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

Déplace le début de la comparaison à une chaîne lexicographique plus tôt lorsque nous trouvons un et Réinitialise tout le reste.

cette section

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

est la partie la plus délicate. Nous avons trouvé une discordance qui est lexicographiquement plus tard que notre chaîne de référence, donc nous passons à la fin du texte correspondant jusqu'à présent, et commençons à correspondre à partir de là. Nous augmentons aussi p (notre foulée). Pourquoi pouvons-nous sauter tous les points de départ entre j et j + k? C'est parce que la chaîne commençant par i est la plus petite lexicographiquement vue, et si la queue de la chaîne j courante est plus grande que la chaîne à i alors tout suffixe de la chaîne à j sera plus grand que la chaîne à i.

Enfin

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

ce juste vérifie que la chaîne de longueur p à partir de i répétitions.Nous procédons en incrémentant k jusqu'à k == p, en vérifiant que le caractère k'th de la chaîne commençant par i est égal au caractère k'th de la chaîne commençant en j. Une fois que k atteint p, nous recommençons le balayage à l'occurrence supposée suivante de la chaîne.

Encore d'autres éditer pour tenter de répondre aux questions de jethro.

Premier: le k != p dans else if (a==b && k!=p) Ici, nous avons une correspondance en ce que le k'th et tous les caractères précédents dans les chaînes commençant par i et j sont égaux. La variable p représente la longueur que nous pensons que la chaîne répétée est. Lorsque k != p, en fait k < p, nous nous assurons que les caractères p sur la chaîne commençant par i sont les mêmes que les p caractères de la chaîne commençant par j. Quand k == p (le dernier) nous devrions être à un point où la chaîne commençant à j + k ressemble à la chaîne commençant par j, donc nous augmentons j par p et redéfinissons k à 1 et revenons à comparer les deux chaînes.

Deuxièmement: Oui, je crois que vous avez raison, il devrait retourner i. Je comprends mal le sens de « décalage cyclique minimum »

Answer 2

Il peut être le même que cet algorithme, dont l'explication se trouve 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; 
}