Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
380226 | Engineering Applications of Artificial Intelligence | 2016 | 6 Pages |
Abstract
A degenerate symbol x˜ over an alphabet Σ is a non-empty subset of Σ, 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Maxime Crochemore, Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, Fatima Vayani,