2010 | OriginalPaper | Chapter
Counting and Verifying Maximal Palindromes
Authors : Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Published in: String Processing and Information Retrieval
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A palindrome is a symmetric string that reads the same forward and backward. Let
pals
(
w
) denote the set of maximal palindromes of a string
w
in which each palindrome is represented by a pair (
c
,
r
), where
c
is the center and
r
is the radius of the palindrome. We say that two strings
w
and
z
are pal-distinct if
pals
(
w
) ≠
pals
(
z
). Firstly, we describe the number of pal-distinct strings, and show that we can enumerate all pal-distinct strings in time linear in the output size, for alphabets of size at most 3. These results follow from a close relationship between maximal palindromes and parameterized matching. Secondly, we present a linear time algorithm which finds a string
w
such that
pals
(
w
) is identical to a given set of maximal palindromes.