Quel est le pire des cas, la complexité de KMP quand le but est de trouver toutes les occurrences d'une chaîne de caractère?
Je voudrais aussi savoir quel algorithme est le pire des cas, la complexité de tous pour trouver toutes les occurrences d'une chaîne dans une autre. Semble Boyer–Moore algorithme a un temps linéaire de la complexité.
Vous devez vous connecter pour publier un commentaire.
Le KMP algorithme a une complexité linéaire pour trouver toutes les occurrences d'un motif dans une chaîne de caractères, comme le Boyer-Moore algorithm1. Si vous essayez de trouver un modèle de type "aaaaaa" dans une chaîne comme "aaaaaaaaa", une fois que vous avez le premier match,
la frontière de la table contient les informations que le côté le plus long possible (correspondant à la plus grande frontière de la forme) d'un préfixe de la forme est juste un caractère court (une correspondance exacte est équivalent à un décalage d'un passé la fin de la tendance à cet égard). Ainsi le motif est déplacée d'un endroit plus et, puisque à partir de la frontière de la table, il est connu que tous les caractères du motif, sauf peut-être le dernier match, la prochaine comparaison entre le dernier modèle de caractère et l'alignement du texte à caractère. Dans ce cas particulier (trouver toutes les occurrences dem dans unn), qui est le pire des cas pour les naïfs algorithme de mise en correspondance, l'algorithme KMP compare chaque caractère du texte exactement une fois.
À chaque étape, au moins un des
augmente, et l'un ne diminue jamais. La position du caractère de texte peut augmenter par rapport à la plupart des
length(text)-1
fois, la position du premier caractère peut augmenter de pluslength(text) - length(pattern)
fois, de sorte que l'algorithme prend au plus2*length(text) - length(pattern) - 1
étapes.Le pré-traitement (construction de la frontière de la table) prend au plus
2*length(pattern)
étapes, ainsi, la complexité est O(m+n) et pas plusm + 2*n
étapes sont exécutées sim
est la longueur du motif etn
la longueur du texte.1 à Noter que les Boyer-Moore algorithme couramment présenté a un pire des cas, la complexité de O(m*n) pour les périodiques des motifs et des textes comme unm etn si tous les matchs sont nécessaires, car après un match,
l'ensemble du motif sera de nouveau par rapport. Pour éviter cela, vous devez vous rappeler combien de temps un préfixe de la motif matches après le passage à la suite d'une correspondance complète et qu'à comparer les nouveaux personnages.
Il y a un long article sur KMP à http://en.wikipedia.org/wiki/Knuth-morris-pratt qui se termine avec le fait de dire
Depuis les deux parties de l'algorithme ont, respectivement, complexité de O(k) et O(n), la complexité globale de l'algorithme est O(n + k).
Ces difficultés sont les mêmes, peu importe combien les motifs répétitifs sont dans W ou S.
(fin de citation)
De sorte que le coût total d'un KMP recherche est linéaire en le nombre de caractères de la chaîne et de modèle. Je pense que cela s'applique même si vous avez besoin de trouver de multiples occurrences du motif dans la chaîne - et si non, il suffit de considérer la recherche de patternQ, où Q est un personnage qui ne se produit pas dans le texte, et de noter où le KMP état montre qu'il correspondait tout à la Q.
Vous pouvez compter Pi fonction d'une chaîne de caractères dans
O(length)
. KMP construit une chaîne de caractères spéciaux qui a une longueurn+m+1
, et compte en fonction de Pi, donc dans tous les cas, la complexité seraO(n+m+1)=O(n+m)