Rotazione lessicografica più piccola di una stringa utilizzando matrici di suffissi in O (n)

Un semplice trucco per costruire tutte le rotazioni di una stringa di lunghezza N è concatenare la stringa con se stessa.

Quindi ogni sottostringa di lunghezza N di questa stringa di lunghezza 2N è una rotazione della stringa originale.

L'individuazione della sottostringa "lessicograficamente minima" viene quindi eseguita con la struttura ad albero O (N).

Sono abbastanza sicuro che le informazioni contenute in un array di suffissi non siano sufficienti per aiutarti a raggiungere O (n), ma al massimo possono aiutarti a O (n log n). Considera questa famiglia di suffissi:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Costruisci il suffisso successivo prendendo il suffisso precedente (ad esempio aba), aggiungendo il carattere successivo non ancora utilizzato e quindi aggiungendo di nuovo il suffisso precedente (quindi aba - > aba c aba).

Ora considera queste stringhe (lo spazio viene aggiunto per enfatizzare, ma non fa parte della stringa):

ad abacaba
bd abacaba
cd abacaba

Per queste tre stringhe, l'inizio dell'array suffisso sarà simile a questo:

a
aba
abacaba
(other suffixes)

Sembra familiare? Queste stringhe ovviamente sono personalizzate per creare questo suffisso array. Ora, a seconda della lettera iniziale (a, b o c), l'indice "corretto" (la soluzione al tuo problema) è il primo, il secondo o il terzo suffisso nell'elenco sopra.

La scelta della prima lettera influisce difficilmente sull'array del suffisso; in particolare, non influisce sull'ordine dei primi tre suffissi dell'array di suffissi. Ciò significa che abbiamo stringhe di log per le quali l'array di suffissi è estremamente simile ma l'indice "corretto" è molto diverso.

Anche se non ho prove concrete, questo mi suggerisce strongmente che non hai altra scelta che confrontare le rotazioni corrispondenti a questi primi tre indici nella matrice per il loro ordinamento lessicografico, che a sua volta significa che avrai bisogno di almeno O (n log n) tempo per questo (poiché il numero di primi caratteri alternativi - nel nostro caso 3 - è log n e il confronto di due stringhe richiede O (n)).

Questo non esclude la possibilità di un algoritmo O (n). Ho solo dubbi sul fatto che un array di suffissi ti aiuti a raggiungere questo tempo di esecuzione.

La rotazione più piccola è quella che inizia con alcuni suffissi dell'array suffisso. I suffissi sono ordinati lessicograficamente. Questo ti dà un grande jumpstart:

• sai che una volta ottenuto tale k quella rotazione che inizia con il suffisso k è minore della rotazione a partire dal suffisso k +1, tu fatto (a partire dal primo);
• puoi fare il confronto tra "rotazione a partire dal suffisso k è minore della rotazione a partire dal suffisso k +1" in O (1) confrontando le lunghezze dei suffissi e opzionalmente, confrontando un carattere con un altro carattere.

EDIT: "un carattere con un altro carattere" potrebbe non essere sempre così, potrebbe essere più di un carattere, ma nel complesso, non si esaminano più di n caratteri attraverso l'intero processo di ricerca, quindi è O (n ).

Prova breve: esaminate solo i caratteri quando il suffisso k +1 è più lungo del suffisso k e vi fermate e trovate la vostra soluzione se suffisso k +1 è più breve del suffisso k (quindi sai che il suffisso k è quello che hai cercato). Quindi esaminate solo i caratteri mentre siete in sequenza di suffissi in aumento (in base alla lunghezza). Poiché esamini solo i caratteri in eccesso, non puoi esaminare più di n caratteri.

EDIT2: questo algoritmo si basa sul fatto che "se ci sono due suffissi vicini nell'array di suffissi e il precedente è più corto del successivo, il precedente è il prefisso del successivo". Se questo non è vero, allora mi dispiace.

EDIT3: No, non regge. "abaaa" ha il suffisso table "a", "aa", "aaa", "abaaa", "baaa". Ma forse questa linea di pensiero può alla fine portare alla soluzione, solo alcuni dettagli devono essere più sofisticati. La domanda principale è se sia possibile in qualche modo effettuare la suddetta comparazione esaminando meno caratteri, quindi è O (n) totalmente, che in qualche modo credo possa essere possibile. Non posso proprio dire come, ora.

Non vedo nulla di meglio di O (N²).

Se hai un elenco di N interi, puoi scegliere il più piccolo tra i confronti O (N).

Qui hai una lista di stringhe N di dimensione N (costruendole non costa nulla, una stringa è completamente determinata dal suo indice iniziale). Puoi scegliere il più piccolo tra i confronti O (N). Ma ogni confronto è O (N) operazioni di base. Quindi la complessità è O (N²).