%0 Journal Article
%T Linear Algorithm for Conservative Degenerate Pattern Matching
%A Maxime Crochemore
%A Costas S. Iliopoulos
%A Ritu Kundu
%A Manal Mohamed
%A Fatima Vayani
%J Computer Science
%D 2015
%I arXiv
%X A degenerate symbol x* over an alphabet A is a non-empty subset of A, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P* and T* of total length n containing k non-solid symbols in total, the occurrences of P* in T* in O(nk) time.
%U http://arxiv.org/abs/1506.04559v1