Discussion :

[kamilia0000]

Bonjour!

Est ce que quelqu'un peut m'expliquer l'algorithme ci-joint

je n'arrive pas a le comprendre

Merci ^_^

[souviron34]

Pourtant c'est correctement expliqué ...

Qu'est-ce que tu ne comprends pas ?

[kamilia0000]

comment i est variable de 1 a n-m+1? ça veut dire quoi (n-m+1)

et l'expression t i+j-1 ==pj veut dire quoi?

[souviron34]

comment i est variable de 1 a n-m+1? ça veut dire quoi (n-m+1)

Faut réfléchir un peu...

p a une longueur m, t une longueur de n..

A partir du moment où on dépasse l'indice n-m+1 dans t, on a forcément plus aucune chance de trouver p.. puisqu'il n'y a plus assez de caractères disponibles..

et l'expression t i+j-1 ==pj veut dire quoi?

noté autrement

t[i+j-1] = p[j]

i est l'indice auquel on a detecté la première lettre commune (la première lettre de p)

De là, on incrémente et t et p , parallèlement, via j.

Si le j-ième caractère de p correspond au j-ième caractère de t (à partir de i), on a bien toujours la sous-chaîne qu'on cherche.

Dès que ce j-ième caractère diffère entre les 2, on ne peut pas avoir p dans t (en tous cas pas à cet endroit-là) : on a juste les (j-1) premiers caractères, sans plus..

Si par contre on atteint la longueur de p (donc j = m+1 avec l'algo), alors on a bien identifié tout p, en entier, commençant à i dans t..

[kamilia0000]

Maintenant c'est claire

Merci beaucoup