Rabin-Karp à la main, et une collision

$H(P)=31415\mathrm{mod}13=7$. Les $15$ fenêtres et leurs empreintes, calculées par la formule de glissement :

i= 0  23590  h= 8      i= 8  41526  h= 4
i= 1  35902  h= 9      i= 9  15267  h= 5
i= 2  59023  h= 3      i=10  52673  h=10
i= 3  90231  h=11      i=11  26739  h=11
i= 4  02314  h= 0      i=12  67399  h= 7  <-- COLLISION
i= 5  23141  h= 1      i=13  73992  h= 9
i= 6  31415  h= 7  <-- OCCURRENCE   i=14  39921  h=11
i= 7  14152  h= 8

Une occurrence (en $i=6$) et une fausse alerte (en $i=12$) : $67399\mathrm{mod}13=7$ également, et pourtant $\text{67399}\ne \text{31415}$.

Ce que la fausse alerte coûte. Elle déclenche une vérification caractère par caractère, $O(m)$. Avec $q=13$, on attend une collision toutes les $13$ fenêtres environ : sur $15$ fenêtres, en avoir une est conforme. Le coût total devient $O(n+\frac{n}{q}m)$, ce qui n'est $O(n+m)$ que si $q$ est grand devant $m$ — d'où le $q=10^9+7$ du chapitre.

Le glissement, vérifié à la main de $i=0$ à $i=1$. On retranche la contribution de la lettre sortante, on décale, on ajoute l'entrante :

$$h_1=((8-2\times 10^4\mathrm{mod}13)\times 10+2)\mathrm{mod}13.$$

Or $10^4\mathrm{mod}13=3$, donc $2\times 3=6$, et $h_1=((8-6)\times 10+2)\mathrm{mod}13=22\mathrm{mod}13=9$. C'est bien la valeur mesurée.

Le point à ne jamais oublier, et le chapitre le met en capitales : l'égalité d'empreintes n'est qu'un filtre. C'est un test qui n'a pas de faux négatif — deux mots égaux ont forcément la même empreinte — mais qui a des faux positifs. Le chapitre chap:probabilistes nommera ce schéma ; le chapitre chap:hachage en donne la cause.