Multiple serial episode matching

Details Multiple serial episode matching Multiple serial episode matching

2006-03-13

arxiv.org/abs/cs/0603050v1

CSIT05 (2005) 26-38

Computer Science

Data Structures and Algorithms

12

Scientific paper

In a previous paper we generalized the Knuth-Morris-Pratt (KMP) pattern matching algorithm and defined a non-conventional kind of RAM, the MP--RAMs (RAMS equipped with extra operations), and designed an O(n) on-line algorithm for solving the serial episode matching problem on MP--RAMs when there is only one single episode. We here give two extensions of this algorithm to the case when we search for several patterns simultaneously and compare them. More preciseley, given $q+1$ strings (a text $t$ of length $n$ and $q$ patterns $m\_1,...,m\_q$) and a natural number $w$, the {\em multiple serial episode matching problem} consists in finding the number of size $w$ windows of text $t$ which contain patterns $m\_1,...,m\_q$ as subsequences, i.e. for each $m\_i$, if $m\_i=p\_1,..., p\_k$, the letters $p\_1,..., p\_k$ occur in the window, in the same order as in $m\_i$, but not necessarily consecutively (they may be interleaved with other letters).} The main contribution is an algorithm solving this problem on-line in time $O(nq)$.

Affiliated with

Also associated with

No associations

Rating

Multiple serial episode matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multiple serial episode matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple serial episode matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-69403