Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.engappai.2016.01.009 | Engineering Applications of Artificial Intelligence |
Keywords | Field | DocType |
Degenerate string,Pattern matching,Algorithm | Degenerate energy levels,Combinatorics,Mathematical optimization,Computer science,Symbol,Linear algorithm,Pattern matching,Alphabet | Journal |
Volume | Issue | ISSN |
51 | C | 0952-1976 |
Citations | PageRank | References |
3 | 0.48 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Ritu Kundu | 3 | 17 | 3.76 |
| Manal Mohamed | 4 | 102 | 12.62 |
| Fatima Vayani | 5 | 25 | 3.85 |