Rotation minimale à l'aide de Suffix array-- Revisited

Question

Considérons une chaîne de longueur n (1 < = n < = 100000). Déterminer sa rotation lexicographique minimale. Par exemple, les rotations de la chaîne « alabala » sont:

alabala 

labalaa 

abalaal 

balaala 

alaalab 

laalaba 

aalabal 

and the smallest among them is “aalabal”. 

Cette question a déjà été posée sur la pile, mais je suis re lui demandant que pas de solution claire est disponible. Jusqu'à présent, j'ai fait des progrès suivants.
1. Prenez S, avec concat inverse (S) .. Soit P = S + marche arrière (S)
tableau suffixe 2.construct de chaîne ci-dessus P

Maintenant, ma question est de savoir si je prends la première chaîne en suffixe tableau de size> strlen(S) puis le préfixe de la taille strlen(S) de cette chaîne sera la rotation minimale de la chaîne donnée S.

Ma conclusion est-elle correcte?

Answer 1

Non, en général, c'est faux (si je comprends bien ce que vous voulez dire). Bien sûr, cela fonctionne bien pour votre entrée palindromique.

Voir la sortie suivante de l'interpréteur python, où les chaînes d'entrée incluent 'alabala' et 'alabatta'. (La sortie a ajouté des espaces et des sauts de ligne.) Dans la deuxième section, la partie avant du premier suffixe plus long que S est inadmissible, c'est-à-dire n'est pas une rotation de S. Voir troisième section pour une approche qui fonctionne.

>>> s = 'alabala'; p = s + ''.join(reversed(s)) 
>>> sorted([p[i:] for i in range(len(p))]) 
['a', 'aalabala', 'abala', 'abalaalabala', 'ala', 'alaalabala', 
'alabala', 'alabalaalabala', 'bala', 'balaalabala', 'la', 
'laalabala', 'labala', 'labalaalabala'] 

>>> s = 'alabatta'; p = s + ''.join(reversed(s)) 
>>> sorted([p[i:] for i in range(len(p))]) 
['a', 'aattabala', 'abala', 'abattaattabala', 'ala', 'alabattaattabala', 
'attaattabala', 'attabala', 'bala', 'battaattabala', 'la', 
'labattaattabala', 'taattabala', 'tabala', 'ttaattabala', 'ttabala'] 

>>> s = 'alabatta'; p = s + s 
>>> sorted([p[i:] for i in range(len(p))]) 
['a', 'aalabatta', 'abatta', 'abattaalabatta', 'alabatta', 
'alabattaalabatta', 'atta', 'attaalabatta', 'batta', 'battaalabatta', 
'labatta', 'labattaalabatta', 'ta', 'taalabatta', 'tta', 'ttaalabatta']