PalFM-index: FM-index for Palindrome Pattern Matching

06/25/2022
βˆ™
by   Shinya Nagashita, et al.
βˆ™
0
βˆ™

Palindrome pattern matching (pal-matching) problem is a generalized pattern matching problem, which searches for the occurrences of substrings in a text that have the same palindromic structure 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, counting queries that compute the number π—ˆπ–Όπ–Ό of the occurrences of P and locating queries that compute the occurrences of P. The authors inΒ [I et al., Theor. Comput. Sci., 2013] proposed O(n n)-bit data structure to support counting queries in O(m Οƒ) time and locating queries in O(m Οƒ + π—ˆπ–Όπ–Ό) time. In this paper, we propose an FM-index type index for pal-matching problem, which we call PalFM-index, that occupies 2n min(Οƒ, n) + 2n + o(n) bits of space and supports counting queries in O(m) time. PalFM-index can support locating queries in O(m + Ξ”π—ˆπ–Όπ–Ό) time by adding n/Ξ” n + n + o(n) bits of space, where Ξ” is a parameter chosen from 1 ≀Δ≀ n.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset