PalFM-index: FM-index for Palindrome Pattern Matching
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