Multiple serial episodes matching |
| |
Authors: | Patrick Cégielski Yuri Matiyasevich |
| |
Affiliation: | a LACL, UMR-FRE 2673, Université Paris 12, Route forestière Hurtault, F-77300 Fontainebleau, France b LIAFA, UMR 7089 and Université Paris 6, 2, Place Jussieu, 75254 Paris Cedex 5, France c Steklov Institute of Mathematics, Fontanka 27, St. Petersburg, Russia |
| |
Abstract: | Given q+1 strings (a text t of length n and q patterns m1,…,mq) and a natural number w, the multiple serial episode matching problem consists in finding the number of size w windows of text t which contain patterns m1,…,mq as subsequences, i.e., for each mi, if mi=p1,…,pk, the letters p1,…,pk occur in the window, in the same order as in mi, but not necessarily consecutively (they may be interleaved with other letters). Our main contribution here is an algorithm solving this problem on-line in time O(nq) with an MP-RAM model (which is a RAM model equipped with extra operations). |
| |
Keywords: | Subsequence matching Algorithms Frequent patterns Episode matching Datamining |
本文献已被 ScienceDirect 等数据库收录! |
|