TY - GEN

T1 - Computing maximal palindromes and distinct palindromes in a trie

AU - Funakoshi, Mitsuru

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Funding Information:
This work was supported by JSPS Grant Numbers JP18K18002 (YN), JP17H01697 (SI), JP16H02783 (HB), and JP18H04098 (MT).
Publisher Copyright:
© Proceedings of the Prague Stringology Conference, PSC 2019. All rights reserved.

PY - 2019

Y1 - 2019

N2 - It is known that all maximal palindromes of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. Also, all distinct palindromes in T can be computed in O(n) time [Groult et al., Inf. Process. Lett. 2010]. In this paper, we consider the problem of computing maximal palindromes and distinct palindromes of a given trie T (i.e. rooted edge-labeled tree). A trie is a natural generalization of a string which can be seen as a single path tree. We propose algorithms to compute all maximal palindromes and all distinct palindromes in T in O(N log h) time and O(N) space, where N is the number of edges in T and h is the height of T . To our knowledge these are the first sub-quadratic time solutions to these problems.

AB - It is known that all maximal palindromes of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. Also, all distinct palindromes in T can be computed in O(n) time [Groult et al., Inf. Process. Lett. 2010]. In this paper, we consider the problem of computing maximal palindromes and distinct palindromes of a given trie T (i.e. rooted edge-labeled tree). A trie is a natural generalization of a string which can be seen as a single path tree. We propose algorithms to compute all maximal palindromes and all distinct palindromes in T in O(N log h) time and O(N) space, where N is the number of edges in T and h is the height of T . To our knowledge these are the first sub-quadratic time solutions to these problems.

UR - http://www.scopus.com/inward/record.url?scp=85086071138&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086071138&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85086071138

T3 - Proceedings of the Prague Stringology Conference, PSC 2019

SP - 3

EP - 15

BT - Proceedings of the Prague Stringology Conference, PSC 2019

A2 - Holub, Jan

A2 - Zdarek, Jan

PB - Prague Stringology Club

T2 - 23rd Prague Stringology Conference, PSC 2019

Y2 - 26 August 2019 through 28 August 2019

ER -