bijour
 
mettons que vous deviez faire un truc cherchant des chaines de caractere dans pas mal de fichier .txt pouvant etre assez volumineux (pas d'ordre de grandeur de taille a donner, désolé), que vous deviez supporter les jokers genre '*' et '?', et que (hallelujah) vous avez droit au gros preprocessing de bourrin.  
 
Avec tout ca en main, vous feriez comment ?
 
Petite precision : la recherche reste 'centrée' sur un mot (les espaces etant des delimiteurs infranchissable pour un pattern de rechecherche, si vous me suivez)
 
 
j'ai trouvé le suffix tree, qui a l'air rigolo mais les jokers passent a la trappe, on dirait (http://www.dogma.net/markn/articles/suffixt/suffixt.htm), idem pour le boyer moore ...
 
Neanmoins, en reflichissant, doit ptet avoir moyen de combiner un peu tout ca (genre chercher les bouts 'sans joker' avec l'aide d'un des deux algos sus-cité puis verifier le mot trouvé a la regexp ou qqchose du genre), mais bon, si vous avez un super algo des familles sous la main...
 
 

Bah déjà, tu peux faire du boyer-moore sur le préfixe (la partie avant le premier joker).
 
Et tu peux utiliser une compilation de regexp (comme le fait boost::regexp je crois) pour le reste.

bin plus sur la plus grande partie du pattern, de recherche sans joker je dirais, plutot que le prefixe (histoire de minimiser les tps de calcul). Sinon pour la compilation de regexp jvais voir (et n'oublions pas que je travaille avec ce merveilleux et moderne langage qu'est le C)

Tu as <regex.h> qui est POSIX avec des extensions GNU sous nunux.

http://es-sun2.fernuni-hagen.de/cg [...] th%20Regex

(je note cette heureuse info, merci)

Comme c'est une sorte d'expression régulière que tu cherches, il n'est pas plus simple de passer par un automate ?

bin heuh, voué, mais le probleme c'est la taille des données, ca risque vite de faire des recherches dans des Mo de texte...

ben avec n'importe quel algo, tu vas bien toujours chercher dans ta tonne de texte. Avec un automate, tu le construis une fois pour toute selon l'expression à rechercher puis tu te ballades entre l'état initial et l'état final (niveau mémoire ça prend rien, niveau temps ca reste du linéaire). Ca me paraît plus simple que de partir sur un algo hybride.

 
Bah non justement, avec Boyer-Moore, le nombre de comparaisons à faire est au mieux N/t (N étant la taille du texte, et t la taille de l'expression à rechercher) (et je suis plus très sûr du cas pire).
 
Donc, si je cherche:
  Abracadabra
Dans le texe:  
  Pluto mange une quenelle
 
La comparaison se fait entre la dernière lettre ("a" ) de mon mot, et le "e" de "mange", puis saute directement au 2ème "l" de "quenelle", puis basta: le mot n'y est pas.

Ouai c'est vrai. Mais va falloir coder un algo hybride pour gérer les joker non ? (automate+boyerMoore)

bin comme dit, utiliser boyermoore pour reperer les "cas possible" avec validation a l'automate. (C'etait ca l'idée, du moins)