Discussion :

[sbadecoder]

Bonjour à tous,

Je recherche un algorithme optimal pour la recherche du mot M dans le texte T (qq Mo).

Le texte T est composé uniquement de lettres 'A'..'Z'.

Le mot S est composé de lettres 'A'..'Z',
mais peut aussi comporter un ou plusieurs '?' (n'importe quelle lettre)...

L'algo devra trouver le plus rapidement possible toutes les occurences du mot M dans le texte T.

[acacia]

Bonsoir,

parcourir le texte lettre par lettre

tester chaque lettre avec la première lettre du mot recherché

si c'est la même tester la suivante.... et ainsi de suite

sinon revenir pour tester avec la première lettre du mot recherché

placer les lettre du mot recherché dans un vecteur avec lequel tu pourras faire le test.

[Jedai]

Bonsoir,

parcourir le texte lettre par lettre

tester chaque lettre avec la première lettre du mot recherché

si c'est la même tester la suivante.... et ainsi de suite

sinon revenir pour tester avec la première lettre du mot recherché

placer les lettre du mot recherché dans un vecteur avec lequel tu pourras faire le test.

Ca c'est l'algorithme naïf et c'est lent. On peut faire beaucoup mieux, par exemple en faisant un automate, on peut passer de O(nm) à O(n).

--
Jedaï

[acacia]

Bonsoir Jedai,

Ca c'est l'algorithme naïf et c'est lent.

--
Jedaï

Je savais qu'on allait me dire ça

par exemple en faisant un automate, on peut passer de O(nm) à O(n)

je trouve l'idée intéressante, mais je ne vois pas très bien comment l'implémenter?

[PRomu@ld]

Pour la culture générale :

http://www-igm.univ-mlv.fr/~lecroq/string/index.html

[sbadecoder]

Ce lien est très interessant mais je ne nage un peu devant tous ces algorithmes...
Lequel est le plus rapide pour moi, en tenant compte du fait que le mot M
peut comporter un ou des '?'.

[pseudocode]

Ce lien est très interessant mais je ne nage un peu devant tous ces algorithmes...
Lequel est le plus rapide pour moi, en tenant compte du fait que le mot M
peut comporter un ou des '?'.

Essaye le "Deterministic Finite Automaton algorithm".

Avec un alphabet de seulement 26 lettres (+ un jocker) ca ne devrait pas etre trop gourmand en mémoire et ca va etre tres rapide.

[Jean-Marc.Bourguet]

Si tu as simplement un ? et pas de *, il devrait etre possible d'adapter Boyer-Moore (ou une variante qui ne degenere pas en nm si les motifs periodiques sont vraissemblables, sinon je ne suis pas sur que ca en vaille la peine).

[sbadecoder]

En fait si le mot M recherché est 'TEXT'
il faut parfois que je recherche aussi
'T?E?X?T', donc une seule lettre entre et jamais de *
et 'T??E??X??T' etc...