License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.15
URN: urn:nbn:de:0030-drops-173006
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17300/
Go to the corresponding LIPIcs Volume Portal

Mieno, Takuya ; Funakoshi, Mitsuru ; Inenaga, Shunsuke

Computing Palindromes on a Trie in Linear Time

pdf-format:
LIPIcs-ISAAC-2022-15.pdf (1 MB)

Abstract

A trie ? is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually distinct. Given a trie ? with n edges, we show how to compute all distinct palindromes and all maximal palindromes on ? in O(n) time, in the case of integer alphabets of size polynomial in n. This improves the state-of-the-art O(n log h)-time algorithms by Funakoshi et al. [PSC 2019], where h is the height of ?. Using our new algorithms, the eertree with suffix links for a given trie ? can readily be obtained in O(n) time. Further, our trie-based O(n)-space data structure allows us to report all distinct palindromes and maximal palindromes in a query string represented in the trie ?, in output optimal time. This is an improvement over an existing (naïve) solution that precomputes and stores all distinct palindromes and maximal palindromes for each and every string in the trie ? separately, using a total O(n²) preprocessing time and space, and reports them in output optimal time upon query.

BibTeX - Entry

@InProceedings{mieno_et_al:LIPIcs.ISAAC.2022.15,
  author =	{Mieno, Takuya and Funakoshi, Mitsuru and Inenaga, Shunsuke},
  title =	{{Computing Palindromes on a Trie in Linear Time}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17300},
  URN =		{urn:nbn:de:0030-drops-173006},
  doi =		{10.4230/LIPIcs.ISAAC.2022.15},
  annote =	{Keywords: palindromes, suffix trees, tries, labeled trees, eertrees}
}

Keywords: palindromes, suffix trees, tries, labeled trees, eertrees
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI