2026-08-06T22:52:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17977 2024-03-06T11:00:46Z ddc:004 open_access

PalFM-Index: FM-Index for Palindrome Pattern Matching Nagashita, Shinya I, Tomohiro Palindrome matching Generalized string pattern matching Indexing The palindrome pattern matching (pal-matching) is a kind of generalized pattern matching, in which two strings x and y of same length are considered to match (pal-match) if they have the same palindromic structures, i.e., for any possible 1 ≤ i < j ≤ |x| = |y|, x[i..j] is a palindrome if and only if y[i..j] is a palindrome. The pal-matching problem is the problem of searching for, in a text, the occurrences of the substrings that pal-match with a pattern. Given a text T of length n over an alphabet of size σ, an index for pal-matching is to support, given a pattern P of length m, the counting queries that compute the number occ of occurrences of P and the locating queries that compute the occurrences of P. The authors in [I et al., Theor. Comput. Sci., 2013] proposed an O(n lg n)-bit data structure to support the counting queries in O(m lg σ) time and the locating queries in O(m lg σ + occ) time. In this paper, we propose an FM-index type index for the pal-matching problem, which we call the PalFM-index, that occupies 2n lg min(σ, lg n) + 2n + o(n) bits of space and supports the counting queries in O(m) time. The PalFM-indexes can support the locating queries in O(m + Δ occ) time by adding n/Δ lg n + n + o(n) bits of space, where Δ is a parameter chosen from {1, 2, … , n} in the preprocessing phase. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shinya Nagashita and Tomohiro I 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.23 urn:nbn:de:0030-drops-179772 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.23 eng https://creativecommons.org/licenses/by/4.0/legalcode