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.2023.23
URN: urn:nbn:de:0030-drops-179772
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17977/
Go to the corresponding LIPIcs Volume Portal

Nagashita, Shinya ; I, Tomohiro

PalFM-Index: FM-Index for Palindrome Pattern Matching

pdf-format:
LIPIcs-CPM-2023-23.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{nagashita_et_al:LIPIcs.CPM.2023.23,
  author =	{Nagashita, Shinya and I, Tomohiro},
  title =	{{PalFM-Index: FM-Index for Palindrome Pattern Matching}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17977},
  URN =		{urn:nbn:de:0030-drops-179772},
  doi =		{10.4230/LIPIcs.CPM.2023.23},
  annote =	{Keywords: Palindrome matching, Generalized string pattern matching, Indexing}
}

Keywords: Palindrome matching, Generalized string pattern matching, Indexing
Collection: 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Issue Date: 2023
Date of publication: 21.06.2023

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