Discussion :

[lapras123]

Re-bonjour, j'au étudié l'algo de :
http://fr.wikipedia.org/wiki/Algorit...h-Pratt-Morris


seulement je comprend pas un passage :

L'exemple précédent illustre de façon instructive le principe de l'algorithme. Il suppose l'existence d'un tabeau donnant les « correspondances partielles » (décrit plus bas), indiquant où chercher le début potentiel de la prochaine occurrence, dans le cas où la vérification de l'occurrence potentielle actuelle échoue. Pour le moment, ce tableau, désigné par T, peut être considéré comme une boîte noire ayant la propriété suivante : si l'on dispose d'une correspondance partielle jusqu'à S[m], mais qui échoue lors de la comparaison entre S[m + 1] et P[i], alors la prochaine occurrence potentielle démarre à la position m + i − T[i − 1]. En particulier, T[ − 1] existe et est défini à − 1

merci de votre aide a +

[Jedai]

En bref tu ne comprends pas le principe de l'algorithme... Regarde, si tu as un mot : "baba".
Tu as déjà trouvé "ba" à la position m de la chaîne (où l'on cherche le mot), mais la lettre suivante n'est pas un "b", alors il est inutile de vérifier à la position m+1 si le mot s'y trouve (puisqu'on sait qu'il y a "a" à cette position, et que le mot commence par "b"), tout comme à la position m+2, finalement il suffit de recommencer la comparaison à la position m+3. Avantage : tu as évité deux comparaisons inutiles.
Tu peux systématiser ce raisonnement, et c'est l'algorithme de KMP. Tu remarqueras que dans mon exemple précédent à aucun moment je ne fais d'hypothèses sur la chaîne autres que les informations fournie par le fait qu'on a échoué lors de la comparaison de la troisième lettre du mot à la position m. Donc le nombre de position à sauter lorsqu'on échoue à la n-ième lettre du mot est une constante ne dépendant que du mot, et pas de la chaîne. Donc on peut construire un tableau du nombre de positions à sauter pour un mot donné si on échoue à sa n-ième lettre.

De toute façon, Jean-Marc.Bourguet utilise Boyer-Moore, qui est un algorithme avec un peu les mêmes idée que KMP (sauf qu'on compare en partant de la fin du mot), mais encore plus efficace (on saute encore plus de comparaison inutiles).

--
Jedaï

[lapras123]

ouais mais j'ai toujours pas compri le principe de remplissage du tableau T[]

Pouvz vous m'expliquer ?

Aussi, quand on utilise un algo comme ca, il est fait pour chercher une chaine bien précise, mais le lien peut etre :
<A
href=lien>
ou

<a dkjkojohigkig href='lien'>


Comment je peux faire pour quand meme récupérer tous les liens ?

bon deja le plus important c'est que j'arrive a appliquer l'algo apres je m'arrangerais, mercio de vos explications sr le T[]

[Jean-Marc.Bourguet]

ouais mais j'ai toujours pas compri le principe de remplissage du tableau T[]

Pouvz vous m'expliquer ?

Je crois que le forum d'algo est fait pour ce genre de question.

Aussi, quand on utilise un algo comme ca, il est fait pour chercher une chaine bien précise, mais le lien peut etre :
<A
href=lien>
ou

<a dkjkojohigkig href='lien'>


Comment je peux faire pour quand meme récupérer tous les liens ?

bon deja le plus important c'est que j'arrive a appliquer l'algo apres je m'arrangerais, mercio de vos explications sr le T[]

Tel que je l'ai compris (mais j'avoue ne pas avoir lu tout le thread), le principe de ce défi est de faire quelque chose de limitté le plus rapide possible, si ce n'était pas le cas je suppose que le test de validation de la page des résultats serait un peu plus complexe.

Sinon, on peut voir KMP comme une version simplifiée de la construction de l'automate déterministe à partir d'une expression rationnelle qui est pour KMP une chaîne constante.

On peut aussi étendre BM et faire sur ce principe des automates traitant des expressions régulières.

[lapras123]

Heu moi j'lai fais a coup de strstr, c'est trop lent ?
je peux le faire en php pour le défi ?
Mon code vous parait il correct mis a part que je travail sur un code source dans un fichier ?