Window-accumulated subsequence matching problem is linear
Luc Boasson, Patrick Cégielski, Irène Guessarian, Yuri Matiyasevich · 1999
Given two strings, text t of length n, and pattern p = p1 : : : pk 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 p1 ; : : : ; pk 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. Keywords: Subsequence matching, algorithms, frequent patterns, episode matching, datamining. 1 Introduction We address the following problem. Given a text t of length n and a pattern p = p 1 \\Delta \\Delta \\Delta p k of l...