Projects per year
Abstract
A degenerate symbol x˜ over an alphabet Σ is a nonempty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of nonsolid symbols is upperbounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first lineartime algorithm that can find, for given degenerate strings P˜ and T˜ of total length n containing k nonsolid symbols in total, the occurrences of P˜ in T˜ in O(nk) time.
Original language  English 

Pages (fromto)  109114 
Number of pages  6 
Journal  ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 
Volume  51 
Early online date  28 Jan 2016 
DOIs  
Publication status  Published  May 2016 
Keywords
 Algorithm
 Degenerate string
 Pattern matching
Fingerprint
Dive into the research topics of 'Linear algorithm for conservative degenerate pattern matching'. Together they form a unique fingerprint.Projects
 1 Finished

Succinct and compressed data structures for string indexing and processing
16/03/2015 → 31/07/2017
Project: Research