Trouvez l'invariant de l'algorithme de Horspool (recherche de motif).

void horspool(char *t, int n, char *p, int m) {
    int d[256];
    for (int i = 0; i < 256; i++) d[i] = m;
    for (int i = 0; i < m-1; i++) d[(unsigned char)p[i]] = m-1-i;
    int k = 0;
    while (k <= n - m) {
        int j = m - 1;
        while (j >= 0 && t[k+j] == p[j]) j--;
        if (j < 0) { /* occurrence trouvée en k */ }
        k += d[(unsigned char)t[k+m-1]];
    }
}

Invariant de boucle :

Valider