[C] BWT, array circolari.

[chicca89]

Ciao a tutti, il mio problema è il seguente: devo far un programmino in c che implementi la bwt, ho già fatto il classico con la matrice di rotazioni ma è abbastanza inefficiente (sprecare n^2 mi sembra troppo!!)
quindi, io ho la stringa in input, volevo confrontarla direttamente con la stringa successiva (slittata di un posto) però in c gli array non sono circolari, giusto? come posso fare?? una volta fatto questo confronto per metterle in ordine lessicografico fino ad ora ho usato il quick sort..non c'è un metodo migliore? perchè così devo fare sempre nxn confronti (2 cicli for annidati)!!
forse non sono stata molto chiara.. grazie per eventuali risposte, mi scuso in anticipo se non sono nella sezione giusta o se ci sono già post a riguardo che mi sono sfuggiti!! grazie!!

[__ZERO_UNO__]

Ciao! Puoi usare i puntatori a carattere. Uno per l'inizio della stringa e uno per la fine. Poi scorri dal puntatore iniziale a quello finale, oppure da quello iniziale alla fine della stringa e poi dall'inizio della stringa al puntatore finale.
Per fare il confronto fra stringhe puoi usare il radix sort che ha costo O(n).

La cosa migliore però è guardare le implementazioni di altri più esperti di noi, che già hanno ragionato su questo problema.