Plus petite rotation lexicographique d'une chaîne utilisant des tableaux de suffixes dans O (n)

Je citerai le problème d'ACM 2003:

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

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

et le plus petit d'entre eux est «aalabal».

Quant à la solution - je sais que je dois construire un tableau de suffixes - et disons que je peux le faire dans O (n). Ma question est toujours, comment puis-je trouver la plus petite rotation dans O (n)? (n = longueur d'une chaîne)

Je suis très intéressé par ce problème et je n'ai toujours pas la solution. Je suis plus intéressé par le concept et la façon de résoudre le problème et non par la mise en œuvre concrète.

Remarque: rotation minimale signifie dans le même ordre que dans un dictionnaire anglais - "dwor" est devant "word" car d est avant w.

EDIT: la construction du tableau de suffixes prend O (N)

DERNIÈRE ÉDITION: Je pense avoir trouvé une solution !!! Et si je fusionnais simplement deux chaînes? Donc, si la chaîne est "alabala", la nouvelle chaîne me "alabalaalabala" et maintenant je construirais simplement un tableau de suffixes (en O (2n) = O (n)) et j'obtiendrais le premier suffixe? Je suppose que cela peut être juste. Qu'est-ce que tu penses? Je vous remercie!

Une astuce simple pour construire toutes les rotations d'une chaîne de longueur N est de concaténer la chaîne avec elle-même.

Ensuite, chaque sous-chaîne de longueur N de cette chaîne de longueur 2N est une rotation de la chaîne d'origine.

La localisation de la sous-chaîne "lexicographiquement minimale" se fait ensuite avec votre construction d'arbre O (N).

Je suis presque sûr que les informations contenues dans un tableau de suffixes ne sont pas suffisantes pour vous aider à accéder à O (n), mais tout au plus peuvent vous aider à O (n log n). Considérez cette famille de suffixes:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Vous construisez le suffixe suivant en prenant le suffixe précédent (disons aba), en ajoutant le caractère suivant non encore utilisé, puis en ajoutant à nouveau le suffixe précédent (donc aba -> aba c aba).

Considérez maintenant ces chaînes (l'espace est ajouté pour l'accentuation, mais ne fait pas partie de la chaîne):

ad abacaba
bd abacaba
cd abacaba

Pour ces trois chaînes, le début du tableau de suffixes ressemblera à ceci:

a
aba
abacaba
(other suffixes)

Ça vous semble familier? Ces chaînes sont bien sûr adaptées pour créer ce tableau de suffixes. Maintenant, selon la lettre de départ (a, b ou c), l'index «correct» (la solution à votre problème) est le premier, le deuxième ou le troisième suffixe dans la liste ci-dessus.

Le choix de la première lettre affecte à peine le tableau des suffixes; en particulier, cela n'affecte pas l'ordre des trois premiers suffixes du tableau de suffixes. Cela signifie que nous avons des chaînes log n pour lesquelles le tableau de suffixes est extrêmement similaire mais l'index «correct» est très différent.

Bien que je n'ai pas de preuve tangible, cela me suggère fortement que vous n'avez pas d'autre choix que de comparer les rotations correspondant à ces trois premiers indices dans le tableau pour leur ordre lexicographique, ce qui signifie que vous aurez besoin d'au moins O (n log n) temps pour cela (car le nombre de premiers caractères alternatifs - dans notre cas 3 - est log n, et la comparaison de deux chaînes prend du temps O (n)).

Cela n'exclut pas la possibilité d'un algorithme O (n). J'ai simplement des doutes qu'un tableau de suffixes vous aide à atteindre ce temps d'exécution.

La plus petite rotation est celle qui commence par une partie du suffixe du tableau de suffixes. Les suffixes sont classés lexicographiquement. Cela vous donne un gros coup de pouce:

• vous savez qu'une fois que vous obtenez un k tel que la rotation commençant par le suffixe k est plus petite que la rotation commençant par le suffixe k +1, vous avez terminé (à partir du premier);
• vous pouvez faire la comparaison de "la rotation commençant par le suffixe k est plus petite que la rotation commençant par le suffixe k +1" dans O (1) en comparant les longueurs des suffixes et éventuellement, en comparant un caractère avec un autre caractère.

EDIT: "un caractère avec un autre caractère" peut ne pas toujours être le cas, il peut y avoir plus d'un caractère, mais dans l'ensemble, vous n'examinez pas plus de n caractères tout au long du processus de recherche, c'est donc O (n).

Preuve courte: vous n'examinez les caractères que lorsque le suffixe k +1 est plus long que le suffixe k , et vous vous arrêtez et trouvez votre solution si le suffixe k +1 est plus court que le suffixe k (alors vous savez que le suffixe k est celui que vous recherchez). Vous n'examinez donc les caractères que lorsque vous êtes dans une séquence ascendante (dans le sens de la longueur) de suffixes. Étant donné que vous examinez uniquement les caractères en excès, vous ne pouvez pas examiner plus de n caractères.

EDIT2: Cet algorithme repose sur le fait que "s'il y a deux suffixes voisins dans le tableau de suffixes et que le précédent est plus court que le suivant, le précédent est le préfixe du suivant". Si ce n'est pas vrai, désolé.

EDIT3: Non, il ne tient pas. "abaaa" a la table des suffixes "a", "aa", "aaa", "abaaa", "baaa". Mais peut-être que cette ligne de pensée peut finalement conduire à la solution, juste quelques détails supplémentaires doivent être plus sophistiqués. La question principale est de savoir s'il est possible de faire en quelque sorte la comparaison susmentionnée en examinant moins de caractères, donc c'est O (n) totalement, ce qui, selon moi, peut être possible. Je ne peux pas dire comment, maintenant.

Problème:

La sous-chaîne le moins circulaire lexicographiquement est le problème de trouver la rotation d'une chaîne possédant l'ordre lexicographique le plus bas de toutes ces rotations. Par exemple, la rotation lexicographiquement minimale de "bbaaccaadd" serait "aaccaaddbb".

Solution:

L'algorithme temporel AO (n) a été proposé par Jean Pierre Duval (1983).

Étant donné deux indices iet j, l'algorithme de Duval compare des segments de chaîne de longueur j - icommençant à iet j(appelé un "duel" ). Si index + j - iest supérieur à la longueur de la chaîne, le segment est formé par enroulement.

Par exemple, considérons s = "baabbaba", i = 5 et j = 7. Puisque j - i = 2, le premier segment commençant à i = 5 est "ab". Le deuxième segment commençant à j = 7 est construit par enroulement et est également "ab". Si les chaînes sont égales lexicographiquement, comme dans l'exemple ci-dessus, nous choisissons celle commençant par i comme gagnante, qui est i = 5.

Le processus ci-dessus s'est répété jusqu'à ce que nous ayons un seul gagnant. Si la chaîne d'entrée est de longueur impaire, le dernier caractère gagne sans comparaison lors de la première itération.

Complexité temporelle:

La première itération compare n chaînes de longueur 1 chacune (n / 2 comparaisons), la deuxième itération peut comparer n / 2 chaînes de longueur 2 (n / 2 comparaisons), et ainsi de suite, jusqu'à ce que la ième itération compare 2 chaînes de longueur n / 2 (comparaisons n / 2). Comme le nombre de gagnants est divisé par deux à chaque fois, la hauteur de l'arbre de récursivité est log (n), nous donnant ainsi un algorithme O (n log (n)). Pour les petits n, c'est approximativement O (n).

La complexité de l'espace est également O (n), car dans la première itération, nous devons stocker n / 2 gagnants, la deuxième itération n / 4 gagnants, etc. (Wikipedia prétend que cet algorithme utilise un espace constant, je ne comprends pas comment).

Voici une implémentation Scala; n'hésitez pas à vous convertir à votre langage de programmation préféré.

def lexicographicallyMinRotation(s: String): String = {
 @tailrec
 def duel(winners: Seq[Int]): String = {
   if (winners.size == 1) s"${s.slice(winners.head, s.length)}${s.take(winners.head)}"
   else {
     val newWinners: Seq[Int] = winners
       .sliding(2, 2)
       .map {
         case Seq(x, y) =>
           val range = y - x
           Seq(x, y)
             .map { i =>
               val segment = if (s.isDefinedAt(i + range - 1)) s.slice(i, i + range)
               else s"${s.slice(i, s.length)}${s.take(s.length - i)}"
               (i, segment)
             }
             .reduce((a, b) => if (a._2 <= b._2) a else b)
             ._1
         case xs => xs.head
       }
       .toSeq
     duel(newWinners)
   }
 }

 duel(s.indices)
}

Je ne vois rien de mieux que O (N²).

Si vous avez une liste de N entiers, vous pouvez choisir le plus petit des comparaisons O (N).

Ici, vous avez une liste de N chaînes de taille N (leur construction ne coûte rien, une chaîne est entièrement déterminée par son index de départ). Vous pouvez choisir le plus petit des comparaisons O (N). Mais chaque comparaison correspond aux opérations de base O (N). La complexité est donc O (N²).