Quel est le moyen le plus efficace de suivre l’index d’un caractère spécifique dans une chaîne ?

Question

Prenons la chaîne suivante comme exemple :

"Le renard brun rapide"

À l'heure actuelle, le q dans quick est à l'index 4 de la chaîne (en commençant à 0) et le f dans fox est à l'index 16.Supposons maintenant que l'utilisateur entre du texte supplémentaire dans cette chaîne.

"Le renard brun foncé très rapide"

Maintenant, le q est à l'index 9 et le f est à l'index 26.

Quelle est la méthode la plus efficace pour garder une trace de l'index du q d'origine dans quick et f dans fox, quel que soit le nombre de caractères ajoutés par l'utilisateur ?

La langue n'a pas d'importance pour moi, c'est plus une question théorique qu'autre chose, alors utilisez la langue de votre choix, essayez simplement de la conserver dans les langues généralement populaires et actuelles.

L'exemple de chaîne que j'ai donné est court mais j'espère trouver un moyen capable de gérer efficacement n'importe quelle taille de chaîne.Ainsi, la mise à jour d'un tableau avec le décalage fonctionnerait avec une chaîne courte mais s'enliserait avec trop de caractères.

Même si dans l'exemple je cherchais l'index des caractères uniques dans la chaîne, je souhaite également pouvoir suivre l'index du même caractère à différents emplacements tels que le o en marron et le o en renard.Il est donc hors de question de chercher.

J'espérais que la réponse serait à la fois efficace en termes de temps et de mémoire, mais si je devais en choisir une seule, je me soucie davantage de la vitesse des performances.

Answer 1

Disons que vous avez une chaîne et que certaines de ses lettres sont intéressant.Pour simplifier les choses, disons que la lettre à l'index 0 est toujours intéressante et que vous n'ajoutez jamais quelque chose avant elle : une sentinelle.Écrivez des paires de (lettre intéressante, distance par rapport à la lettre intéressante précédente).Si la chaîne est "+le renard brun foncé très rapide" et que vous êtes intéressé par q de "quick" et f de "fox", alors vous écririez :(+,0), (q,10), (f,17).(Le signe + est la sentinelle.)

Maintenant, vous les placez dans un arbre binaire équilibré dont le parcours dans l'ordre donne la séquence de lettres dans l'ordre dans lequel elles apparaissent dans la chaîne.Vous pourriez maintenant reconnaître le problème de sommes partielles:Vous agrémentez l'arbre pour que les nœuds contiennent (lettre, distance, somme).La somme est la somme de toutes les distances dans le sous-arbre de gauche.(Donc somme(x)=distance(gauche(x))+somme(gauche(x)).)

Vous pouvez désormais interroger et mettre à jour cette structure de données en temps logarithmique.

Dire que tu as ajouté n caractères à gauche du personnage c vous dites distance(c)+=n puis allez mettre à jour la somme pour tous les parents de c.

Pour demander quel est l'indice de c vous calculez sum(c)+sum(parent(c))+sum(parent(parent(c)))+...

Answer 2

Votre question est un peu ambiguë : cherchez-vous à garder une trace des premières instances de chaque lettre ?Si tel est le cas, un tableau de longueur 26 pourrait être la meilleure option.

Chaque fois que vous insérez du texte dans une chaîne à une position inférieure à l'index dont vous disposez, calculez simplement le décalage en fonction de la longueur de la chaîne insérée.

Answer 3

Il serait également utile que vous ayez une langue cible en tête, car toutes les structures de données et interactions ne sont pas également efficaces dans toutes les langues.

Answer 4

L'astuce standard qui aide généralement dans des situations similaires consiste à conserver les caractères de la chaîne sous forme de feuilles dans un arbre binaire équilibré.De plus, les nœuds internes de l'arborescence doivent conserver des ensembles de lettres (si l'alphabet est petit et fixe, il peut s'agir de bitmaps) qui apparaissent dans le sous-arbre enraciné à un nœud particulier.

L'insertion ou la suppression d'une lettre dans cette structure ne nécessite que des opérations O(log(N)) (mettre à jour les bitmaps sur le chemin vers la racine) et trouver la première occurrence d'une lettre nécessite également des opérations O(log(N)) - vous descendez de la racine, en allant vers l'enfant le plus à gauche dont le bitmap contient la lettre intéressante.

Modifier:Les nœuds internes doivent également conserver le nombre de feuilles dans le sous-arbre représenté, pour un calcul efficace de l'index de la lettre.