Irène Guessarian (LIAFA-Paris7 et Universite Paris 6)

Etant donnes deux mots, un texte t de longueur n, et un motif p=p1… pk de longueur k, et etant donne un entier w, le problme du “subsequence matching” (ou appariement de sous-mots) consiste en la recherche du nombre de fenetres de taille w du texte t contenant le motif p comme sous-mot, i.e. les lettres p1,…,pk sont dans la fenetre, dans le meme ordre que dans p, mais peuvent ne pas etre consecutives (elles peuvent etre intercalees avec d’autres lettres). L’appariement de sous-mots est utilise pour determiner les motifs frequents et les regles d’association dans les bases des donnees. Nous generalisons l’algorithme d’appariement de motif de Knuth-Morris-Pratt; nous d%GŽ%@finissons des machines RAM non-classiques, que nous appelons machines MP–RAM, et qui modelisent les operations des microprocesseurs mieux que les machines RAM; nous donnons un algorithme en ligne et en temps O(n) qui resout le probleme de l’appariement de sous-mots sur une machine MP–RAM.

(travail commun avec Luc Boasson, Patrick Cegielski, Yuri Matiyasevich)