Bonjour à tous,

je suis en train d'implémenter des algorithmes dans le cadre d'un travail sur le Pattern Matching with Don't Cares (en français la recherche de motif dans un texte avec un caractère "joker")
Ce domaine utilise énormément de calcul de FFT et de convolution malheureusement je dois dire que je patauge un peu là dedans

Par exemple, je suis plongé dans l'algorithme de Kalai http://people.cs.uchicago.edu/~kalai/PAPERS/dontcare.ps. Celui-ci indique qu'il faut calculer une somme de produit à l'aide de FFT:

soit une chaine de caractères: X=x1....xn et une chaine d'entier R=r1....rm (m<n)
il faut calculer:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
Somme de i=1 à m de:  x_{j-1+i}r_{i}
où pourrais-je trouver une librairie (ou un algo) me permettant de résoudre ce genre de calcul? Toutes les implémentations de FFT que j'ai pu trouver sur le net servent à traiter des signaux et des échantillonages. J'ai bien compris le lien qui existe entre la multiplication de grands entiers et le calcul de FFT (http://en.wikipedia.org/wiki/Multiplication_algorithm mais je ne vois pas comment l'adapter à mon problème

merci d'avance à ceux qui pourront m'aider

PS: je code ces algos en c++