Linear algorithm for conservative degenerate pattern matching

TY - JOUR

T1 - Linear algorithm for conservative degenerate pattern matching

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Kundu, Ritu

AU - Mohamed, Manal

AU - Vayani, Fatima

PY - 2016/5

Y1 - 2016/5

N2 - 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.

AB - 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.

KW - Algorithm

KW - Degenerate string

KW - Pattern matching

UR - https://www.scopus.com/pages/publications/84961599127

U2 - 10.1016/j.engappai.2016.01.009

DO - 10.1016/j.engappai.2016.01.009

M3 - Article

AN - SCOPUS:84961599127

SN - 0952-1976

VL - 51

SP - 109

EP - 114

JO - ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

JF - ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

ER -