2026-07-22T22:17:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13974 2024-03-06T10:53:02Z ddc:004 open_access

Efficient Algorithms for Counting Gapped Palindromes Popa, Andrei Popa, Alexandru pattern matching gapped palindromes suffix tree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei Popa and Alexandru Popa 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.23 urn:nbn:de:0030-drops-139746 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.23 eng https://creativecommons.org/licenses/by/4.0/legalcode