Spiegazione algoritmo minimo spostamento ciclico

Question

Recentemente mi sono imbattuto in questo codice privo di commenti. Trova uno spostamento ciclico minimo della parola (questo codice restituisce specificamente il suo indice in stringa) e il suo algoritmo chiamato Duval. Solo info ho trovato descrive l'algoritmo in poche parole e ha un codice più pulito. Gradirei qualsiasi aiuto nella comprensione di questo algoritmo. Ho sempre trovato gli algoritmi testuali piuttosto complicati e piuttosto difficili da capire.

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

In primo luogo, credo che il tuo codice abbia un bug in esso. L'ultima riga deve essere return p;. Credo che detenga l'indice del turno ciclico lessicograficamente più piccolo, e p detiene il minimo spostamento corrispondente. Penso anche che la tua condizione di arresto sia troppo debole, cioè stai facendo troppi controlli dopo aver trovato una corrispondenza, ma non sono sicuro di cosa dovrebbe essere esattamente.

Si noti che i e j solo anticipo e che i è sempre meno di j. Stiamo cercando una stringa che corrisponda alla stringa che inizia con i, e stiamo cercando di abbinarla con una stringa che inizia con j. Lo facciamo confrontando il carattere k'th di ogni stringa aumentando k (purché corrispondano). Notate che cambiamo i solo se determiniamo che la stringa che inizia in j è lessicograficamente inferiore alla stringa che inizia con j, e quindi impostiamo i in j e resettiamo k e p ai loro valori iniziali.

io non ho tempo per un'analisi dettagliata, ma sembra che

1. i = l'inizio della lessicografico più piccolo spostamento ciclico
2. j = l'inizio dello spostamento ciclico ci sono corrispondenti contro il spostare a partire da
3. k = carattere nelle stringhe i e j attualmente sotto esame (partita stringhe nelle posizioni 1 a k-1
4. p = spostamento ciclico in esame (credo p significa prefisso)

Modifica Proseguendo

questa sezione di codice

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

Sposta l'inizio del confronto in una stringa lessicografico prima, quando troviamo uno e reinizializza tutto il resto.

questa sezione

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

è la parte difficile. Abbiamo trovato una mancata corrispondenza che è lessicograficamente più tardi della nostra stringa di riferimento, quindi salta alla fine del testo corrispondente finora e inizia la corrispondenza da lì. Aumentiamo anche p (il nostro passo). Perché possiamo saltare tutti i punti di partenza tra j e j + k? Questo perché la stringa che inizia con i è il lessicograficamente più piccolo visto, e se la coda della stringa j corrente è maggiore allora la stringa in i quindi qualsiasi suffisso della stringa in j sarà maggiore della stringa in i.

Infine

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

questo solo controlla che la stringa di lunghezza p a partire da ripetizioni.

** ulteriormente modificare * Facciamo questo incrementando k fino k == p, controllando che il carattere k'th della stringa a partire da uguale al carattere k'th della stringa a partire da j. Una volta che k raggiunge p iniziamo nuovamente la scansione alla supposta occorrenza successiva della stringa.

Modificare ulteriormente per tentare di rispondere alle domande di jethro.

Primo: lo k != p in else if (a==b && k!=p) Qui abbiamo una corrispondenza in cui il k'th e tutti i precedenti caratteri nelle stringhe che iniziano con i e j sono uguali. La variabile p rappresenta la lunghezza che pensiamo sia la stringa ripetitiva. Quando, in realtà k < p, ci assicuriamo che i caratteri p della stringa che iniziano con i siano gli stessi dei caratteri p della stringa che inizia con j. Quando k == p (l'ultimo) dovremmo trovarci in un punto in cui la stringa che inizia a j + k è uguale alla stringa che inizia da j, quindi aumentiamo j per p e riportiamo k a 1 e torniamo a confrontare le due stringhe.

Secondo: Sì, credo che tu abbia ragione, dovrebbe restituirmi. Stavo equivoco il significato di "spostamento ciclico minimo"

Answer 2

Può essere lo stesso di questo algoritmo, la cui spiegazione può essere trovata 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; 
}