License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2021.23
URN: urn:nbn:de:0030-drops-139746
Go to the corresponding LIPIcs Volume Portal

Popa, Andrei ; Popa, Alexandru

Efficient Algorithms for Counting Gapped Palindromes

LIPIcs-CPM-2021-23.pdf (0.7 MB)


A gapped palindrome is a string uvu^{R}, where u^{R} represents the reverse of string u. In this paper we show three efficient algorithms for counting the occurrences of gapped palindromes in a given string S of length N. First, we present a solution in O(N) time for counting all gapped palindromes without additional constraints. Then, in the case where the length of v is constrained to be in an interval [g, G], we show an algorithm with running time O(N log N). Finally, we show an algorithm in O(N log² N) time for a more general case where we count gapped palindromes uvu^{R}, where u^{R} starts at position i with g(i) ≤ v ≤ G(i), for all positions i.

BibTeX - Entry

  author =	{Popa, Andrei and Popa, Alexandru},
  title =	{{Efficient Algorithms for Counting Gapped Palindromes}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-139746},
  doi =		{10.4230/LIPIcs.CPM.2021.23},
  annote =	{Keywords: pattern matching, gapped palindromes, suffix tree}

Keywords: pattern matching, gapped palindromes, suffix tree
Collection: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Issue Date: 2021
Date of publication: 30.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI