Ceci est purement hors de curiosité. Je parcourais un article en comparant divers algorithmes de recherche de chaînes et que je me suis remarqué, ils étaient tous conçus pour trouver la première sous-chaîne correspondante. Cela m'a fait penser ... Et si je voulais trouver toutes les occurrences d'une sous-chaîne?
Je suis sûr que je pouvais créer une boucle qui utilisait une variante de KMP ou BM et jeté de l'occurrence trouvée à une matrice, mais cela semble à peine comme si ce serait le plus rapide.
ne serait pas un algorithme de division et de conquête de conquérir?
Par exemple, disons que vous recherchez la séquence "ABC" dans une chaîne "ABBCACABBCACACBCCBABC".
Considérant la facilité avec laquelle je suis venu avec cette idée que je suppose que quelqu'un est déjà venu avec elle et l'améliore il y a 30 ans.
4 Réponses :
a) Quelle est la chaîne en réalité de (longueur, distribution de caractères, ...)
B) sur quel matériel cela fonctionne
c) si vous voulez tous les résultats en parallèle ou séquentiel
d) D'autres paramètres (par exemple, des éléments de chevauchement des éléments trouvés, recherchez-vous une fois ou plusieurs fois)
e) Si vous voyez cette implémentation spécifique ou juste universitaire. En mettant en œuvre, il y a beaucoup de moyens supplémentaires d'optimiser les choses. Par exemple. Le stockage temporaire (comme dans votre suggestion) est souvent très coûteux.
L'idée que vous avez par exemple. déduirait totalement n'importe quel cache de processeur pour les longues chaînes. Donc, ce serait très lent dans ces cas.
voir Suffix Array
applications
Le remplissage de suffixe d'une chaîne peut être utilisé comme index pour localiser rapidement chaque apparition d'une sous-chaîne dans la chaîne. Trouver tous les événements de la sous-chaîne équivaut à trouver chaque suffixe qui commence par la sous-chaîne. Grace à Commande lexicographique, ces les suffixes seront regroupés dans le comprimé suffixe, et peut être trouvé efficacement avec une recherche binaire. Si mis en œuvre directement, cette La recherche binaire prend une heure (mlogn), où m est la longueur de la Substrage. Pour éviter de refaire Comparaisons, structures de données supplémentaires donner des informations sur le plus long Les préfixes communes (LCP) de suffixes sont construit, donnant o (m + logn) recherche temps.
Si vous ne traiterez qu'une chaîne donnée une fois, la matrice suffixe est surchargée. Il faut une heure de création d'un algorithme de style KMP. De plus, si votre chaîne est énorme ou si vous souhaitez obtenir des résultats en temps réel pendant que vous recevez la chaîne, le réseau suffixe ne fonctionnera pas.
Il est certainement possible de modifier l'algorithme KMP pour continuer à aller après avoir trouvé une correspondance sans prendre de mémoire supplémentaire, à part la mémoire utilisée pour stocker les matchs (ce qui peut être inutile également, si vous imprimez simplement les matchs ou les traiter comme vous suivez). Comme un démarrage, prenez le Mise en œuvre Wikipedia et modifier le "retour m "Déclaration" ajouter M à une liste d'index ". Mais vous n'êtes pas encore fait. Vous devez également vous demander, permettez-vous d'occurrences qui se chevauchent? Par exemple, si votre sous-chaîne est "abab" et que vous recherchez dans la chaîne principale "abababab", y a-t-il deux occurrences ou trois? Dans l'exemple que j'ai donné ("comme un démarrage"), vous pouvez soit réinitialiser i à 0 pour donner la réponse "Deux", ou pour que vous puissiez tomber à l'affaire "Sinon" après le "Ajouter M" pour donner les "trois "Réponse.
Le KMP et BM peuvent facilement être utilisés pour trouver également plusieurs matchs. Je recommanderais également d'utiliser RABIN-KARP , que IMHO est plus facile à comprendre mais pas vraiment Comme rapide pour plusieurs correspondances (O (N + K * M), je pense, où n est la longueur du texte, m est la longueur du motif et k est le nombre d'occurrences). Mais il est facile de modifier pour les allumettes de chevauchement et de chevauchement.
Il peut également être fait en utilisant des tableaux d'arbres / suffixe suffixe, mais ils sont plus difficiles à coder et ne vous achètent pas vraiment d'augmentation de la vitesse.
Ça dépend. Si vous avez la chaîne "aaaaaa" combien de "aa" sont là? 3? 5? Cela dépend également de la langue que vous utilisez.