1
T:String
P:pattern
ce qui est le maximum pas de fois un caractère particulier dans une chaîne (T) dans Knuth morris algorithme pratt entre en comparaison avec le motif (P)?
A
Répondre
0
|P|. Voici un exemple:
P = aaa...a(n times) T = aaa...a(n times)b
Quand on arrive à b, la valeur courante du compteur est n. Chaque comparaison le diminue d'exactement un. Ainsi, il fait exactement n itérations jusqu'à ce qu'il atteigne zéro.
Pourquoi est-ce une limite supérieure?
Il est évident que le nombre de comparaisons est au plus de |P| (chaque comparaison diminue la valeur de la fonction de préfixe d'au moins un et ne peut jamais dépasser |P|).
et si la chaîne P = abababab et le patron T = abc alors ne pensez-vous pas que après le premier a tout est comparé 2 fois? – asadkaramat