Fonction Z pour rechercher un motif

La fonction Z est une solution élégante qui constitue une alternative à KMP pour rechercher un motif. Beaucoup la trouvent plus facile à comprendre. ✨

Pour chaque indice, z[i] est la longueur de la plus longue sous-chaîne commençant à l’indice i qui correspond également à un préfixe de la chaîne entière.

Pour aabaab, z vaut 0,1,0,3,1,0. À l’indice 3, la séquence aab correspond au préfixe, ce qui donne une longueur de 3.

Nous suivons une fenêtre [l, r], qui contient la correspondance la plus à droite trouvée jusqu’à présent. Elle nous permet de réutiliser les comparaisons précédentes.

Lorsque i se trouve dans la boîte, vous copiez une valeur de z connue comme point de départ, en la limitant par le bord de la boîte.

Après ce point de départ, vous continuez à comparer les caractères un par un tant qu’ils correspondent au préfixe.

Si votre correspondance va plus loin vers la droite, vous mettez à jour l et r afin que les indices suivants puissent la réutiliser.

La boîte se déplace uniquement vers la droite, donc le travail total est de O(n). Chaque caractère contribue dans une quantité limitée.

Concaténez pattern + sep + text, puis appliquez Z. Toute valeur de z égale à la longueur du motif indique une correspondance.

Parcourez le tableau Z ; partout où z[i] == len(pattern), la correspondance commence à la position correspondante dans le texte.

Z et KMP s’exécutent tous deux en temps linéaire. Z est souvent plus simple à coder, ce qui en fait une excellente solution de secours dans votre boîte à outils.

Assurez-vous d’avoir bien compris la signification du tableau Z.

Vous avez construit le tableau Z avec une boîte coulissante, effectué une recherche en temps linéaire et disposez maintenant d’une alternative élégante à KMP. 🎯