Bonsoir à tous.
Je travaille actuellement sur la recherche de chaîne et notamment sur l'algorithme de Rabin Karp

L'idée de l'algorithme est de transformer le motif de longeur M que l'on recherche dans notre texte de longeur N en adresse par un processus de hachage. Ensuite on hache les M premiers caractères de notre texte et on voit si il y a correspondance. Le code est le suivant en langage C:

#define q 33554393
#define d 32

int rechercherRK(char* p,char* t)
{
    int i,dM=1,h1=0,h2=0;
    int M=strlen(p),N=strlen(t);

    for (i=1;i<M;i++) dM=(d*dM)%q;
    for (i=0;i<M;i++)
    {
        h1=(h1*d+Indice(p[i]))%q;
        h2=(h2*d+Indice(t[i]))%q;
    }
    
    for (i=0;h1!=h2;i++)
    {
        h2=(h2+d*q-Indice(t[i])*dM)%q;
        h2=(h2*d+Indice(t[i+M]))%q;
        
        if (i>N-M) return N;
    }
    return i;

}

L'algorithme  crée donc des adresses à partir de chaîne de caractère, ca ok. Mais il y a 2 points qui me chiffonnent:

1) Dans tous les articles que j'ai lu ils disent qu'il faut choisir q de telle manière que (d+1)*q ne provoque pas de dépassement

je comprends pas bien pourquoi il faut faire (d+1)*q pour voir si il y a dépassement et j'avoue pas très bien comprendre la notion

de dépassement.

2) Dans l'algo on rajoute dans la 3eme boucle for un d*q qui permet d'avoir un reste positif. Que le reste soit toujours

positif je comprends, mais le fait de rajouter d*q ne risque t-il pas de "fausser" l'adresse que l'on trouve pour h2 et

d'entraîner h2!=h1 alors que les caractères concordent?

Merci si vous pouvez répondre à ces questions et bonne continuation.