Searching for Ephemeral Subsequences in Strings
Alberto Apostolico, Mikhail J. Attalah · Purdue e-Pubs (Purdue University System) · 1996
Let T = u, ... Un be a text where every symbol Uj has a time slamp t, and a duration d(ai) a.s.sociatcd with it.The time stamps of the ai's are increasing, so that j > i implies tj > li.A text. symbol OJ is alive.at time tiff tj :S t:S t; + d(u;).A subsequence ai, ... OJ ... of T is alive iff every Gi k is alive at time tim.' that is.ti k + d(ai.)~tim for all k E {I, ... I m -I}.We consider the problem of determining whether a given pattern P == h ... b m occurs as an alive subsequence ofT.We give an off-line (i.e., the pattern is known in advance) algorithm, running in O(n+m) time.We also introduce and discuss data structures for fast on-line implementation.