2010 | OriginalPaper | Buchkapitel
Counting and Verifying Maximal Palindromes
verfasst von : Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.