1 Search Results for "Popa, Andrei"


Document
Efficient Algorithms for Counting Gapped Palindromes

Authors: Andrei Popa and Alexandru Popa

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)


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

Cite as

Andrei Popa and Alexandru Popa. Efficient Algorithms for Counting Gapped Palindromes. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{popa_et_al:LIPIcs.CPM.2021.23,
  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 =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.23},
  URN =		{urn:nbn:de:0030-drops-139746},
  doi =		{10.4230/LIPIcs.CPM.2021.23},
  annote =	{Keywords: pattern matching, gapped palindromes, suffix tree}
}
  • Refine by Author
  • 1 Popa, Alexandru
  • 1 Popa, Andrei

  • Refine by Classification
  • 1 Theory of computation → Pattern matching

  • Refine by Keyword
  • 1 gapped palindromes
  • 1 pattern matching
  • 1 suffix tree

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail