LIPIcs.ISAAC.2022.15.pdf
- Filesize: 1.38 MB
- 15 pages
Document
Computing Palindromes on a Trie in Linear Time
Authors
Takuya Mieno 
,
Mitsuru Funakoshi ,
Shunsuke Inenaga
-
Part of:
Volume:
33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
- Department of Computer and Network Engineering, University of Electro-Communications, Tokyo, Japan
- Department of Informatics, Kyushu University, Fukuoka, Japan
- Japan Society for the Promotion of Science, Tokyo, Japan
Acknowledgements
We would like to thank anonymous referees for their helpful comments. We also thank Takuya Matsumoto for discussions.
Cite AsGet BibTex
Takuya Mieno, Mitsuru Funakoshi, and Shunsuke Inenaga. Computing Palindromes on a Trie in Linear Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.15
https://doi.org/10.4230/LIPIcs.ISAAC.2022.15
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Pattern matching
Keywords
- palindromes
- suffix trees
- tries
- labeled trees
- eertrees
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In 4th Latin American Theoretical Informatics Symposium, LATIN 2000, volume 1776 of Lecture Notes in Computer Science, pages 88-94. Springer, 2000. URL: https://doi.org/10.1007/10719839_9.
- Michael A. Bender and Martin Farach-Colton. The level ancestor problem simplified. Theor. Comput. Sci., 321(1):5-12, 2004. URL: https://doi.org/10.1016/j.tcs.2003.05.002.
- Dany Breslauer. The suffix tree of a tree and minimizing sequential transducers. Theor. Comput. Sci., 191(1-2):131-144, 1998. URL: https://doi.org/10.1016/S0304-3975(96)00319-2.
- Srecko Brlek, Nadia Lafrenière, and Xavier Provençal. Palindromic complexity of trees. In 19th International Conference on Developments in Language Theory, DLT 2015, volume 9168 of Lecture Notes in Computer Science, pages 155-166. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21500-6_12.
- Xavier Droubay, Jacques Justin, and Giuseppe Pirillo. Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci., 255(1-2):539-553, 2001. URL: https://doi.org/10.1016/S0304-3975(99)00320-5.
- Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. J. ACM, 47(6):987-1011, 2000. URL: https://doi.org/10.1145/355541.355547.
- Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing maximal palindromes and distinct palindromes in a trie. In Proceedings of the Prague Stringology Conference, PSC 2019, pages 3-15. Czech Technical University in Prague, Faculty of Information Technology, Department of Theoretical Computer Science, 2019. URL: http://www.stringology.org/event/2019/p02.html.
- Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, and Tomasz Walen. Tight bound for the number of distinct palindromes in a tree. In 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015, volume 9309 of Lecture Notes in Computer Science, pages 270-276. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-23826-5_26.
- Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, and Tomasz Walen. Tight bound for the number of distinct palindromes in a tree. CoRR, abs/2008.13209, 2020. URL: https://doi.org/10.48550/arXiv.2008.13209.
- Richard Groult, Élise Prieur, and Gwénaël Richomme. Counting distinct palindromes in a word in linear time. Inf. Process. Lett., 110(20):908-912, 2010. URL: https://doi.org/10.1016/j.ipl.2010.07.018.
- Dan Gusfield. Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press, 1997. URL: https://doi.org/10.1017/cbo9780511574931.
- Shunsuke Inenaga. Towards a complete perspective on labeled tree indexing: New size bounds, efficient constructions, and beyond. J. Inf. Process., 29:1-13, 2021. URL: https://doi.org/10.2197/ipsjjip.29.1.
- S. Rao Kosaraju. Efficient tree pattern matching (preliminary version). In 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pages 178-183. IEEE Computer Society, 1989. URL: https://doi.org/10.1109/SFCS.1989.63475.
- Glenn K. Manacher. A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string. J. ACM, 22(3):346-351, 1975. URL: https://doi.org/10.1145/321892.321896.
- Mikhail Rubinchik and Arseny M. Shur. EERTREE: an efficient data structure for processing palindromes in strings. Eur. J. Comb., 68:249-265, 2018. URL: https://doi.org/10.1016/j.ejc.2017.07.021.
- Tetsuo Shibuya. Constructing the suffix tree of a tree with a large alphabet. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 86-A(5):1061-1066, 2003. URL: http://search.ieice.org/bin/summary.php?id=e86-a_5_1061.
-
Wing-Kin Sung. Algorithms in Bioinformatics: A Practical Introduction. Chapman and Hall/CRC, 2009.
- Peter Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on Switching and Automata Theory, SWAT 1973, pages 1-11. IEEE Computer Society, 1973. URL: https://doi.org/10.1109/SWAT.1973.13.