Le WASP (Window-Accumulated Subsequence matching Problem) est linéaire
Irène Guessarian
(Travail en collaboration avec Luc Boasson, Patrick Cegielski et Yuri
Matiyasevich )
(LIAFA, Paris)
Abstract:
Given two strings, text t of length n, and pattern
of length k, and given a natural number w, the subsequence
matching problem consists in finding the number of size w windows
of text t which contain pattern p as a subsequence, i.e.
the letters
occur in the window, in the same order as in p, but not necessarily
consecutively (they may be interleaved with other letters). Subsequence
matching is used for finding frequent patterns and association rules in
databases. We generalize the Knuth-Morris-Pratt (KMP) pattern matching
algorithm; we define a non-conventional kind of RAM, the MP-RAMs which
model more closely the microprocessor operations; we design an O(n)
on-line algorithm for solving the subsequence matching problem on MP-RAMs.