Efficient pattern matching in elastic-degenerate strings

Costas S. Iliopoulos, Ritu Kundu*, Solon P. Pissis

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Article number104616
Publication statusAccepted/In press - 1 Jan 2020


  • Algorithms on strings
  • Degenerate strings
  • Elastic-degenerate strings
  • Gapped strings
  • Indeterminate strings


Dive into the research topics of 'Efficient pattern matching in elastic-degenerate strings'. Together they form a unique fingerprint.

Cite this