King's College London

Research portal

Linear algorithm for conservative degenerate pattern matching

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)109-114
Number of pages6
JournalENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
Volume51
Early online date28 Jan 2016
DOIs
Publication statusPublished - May 2016

King's Authors

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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454