2020
Efficient pattern matching in elastic-degenerate strings
Publication
Publication
Information and Computation , Volume 276 p. 104616
Motivated by applications in bioinformatics and image searching, in what follows, we study the classic pattern matching problem in the context of elastic-degenerate strings: the generalised notion of gapped strings. An elastic-degenerate string can be seen as an ordered collection of k strings interleaved by k−1 elastic-degenerate symbols, where each such elastic-degenerate symbol corresponds to a set of two or more variable-length strings. We present efficient algorithms for two variants of the pattern matching problem on elastic-degenerate strings: first, for a solid pattern and an elastic-degenerate text; second, for an elastic-degenerate pattern and a solid text. A proof-of-concept implementation of the former is provided.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1016/j.ic.2020.104616 | |
| Information and Computation | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Iliopoulos, C., Kundu, R., & Pissis, S. (2020). Efficient pattern matching in elastic-degenerate strings. Information and Computation, 276. doi:10.1016/j.ic.2020.104616 |
|
