Online Computation of Palindromes and Suffix Trees on Tries
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917219400679424 |
|---|---|
| author | Shibata, Hiroki Funakoshi, Mitsuru Mieno, Takuya Ishihata, Masakazu Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki |
| author_facet | Shibata, Hiroki Funakoshi, Mitsuru Mieno, Takuya Ishihata, Masakazu Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki |
| contents | We consider the problems of computing maximal palindromes and distinct palindromes in a trie. A trie is a natural generalization of a string, which can be seen as a single-path tree. There is a linear-time offline algorithm to compute maximal palindromes and distinct palindromes in a given (static) trie whose edge-labels are drawn from a linearly-sortable alphabet [Mieno et al., ISAAC 2022]. In this paper, we tackle problems of palindrome enumeration on dynamic tries which support leaf additions and leaf deletions. We propose the first sub-quadratic algorithms to enumerate palindromes in a dynamic trie. For maximal palindromes, we propose an algorithm that runs in $O(N \min(\log h, σ))$ time and uses $O(N)$ space, where $N$ is the maximum number of edges in the trie, $σ$ is the size of the alphabet, and $h$ is the height of the trie. For distinct palindromes, we develop several online algorithms based on different algorithmic frameworks, including approaches using the EERTREE (a.k.a. palindromic tree) and the suffix tree of a trie. These algorithms support leaf insertions and deletions in the trie and achieve different time and space trade-offs. Furthermore, as a by-product, we present online algorithms to construct the suffix tree and the EERTREE of the input trie, which is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16485 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Online Computation of Palindromes and Suffix Trees on Tries Shibata, Hiroki Funakoshi, Mitsuru Mieno, Takuya Ishihata, Masakazu Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Data Structures and Algorithms We consider the problems of computing maximal palindromes and distinct palindromes in a trie. A trie is a natural generalization of a string, which can be seen as a single-path tree. There is a linear-time offline algorithm to compute maximal palindromes and distinct palindromes in a given (static) trie whose edge-labels are drawn from a linearly-sortable alphabet [Mieno et al., ISAAC 2022]. In this paper, we tackle problems of palindrome enumeration on dynamic tries which support leaf additions and leaf deletions. We propose the first sub-quadratic algorithms to enumerate palindromes in a dynamic trie. For maximal palindromes, we propose an algorithm that runs in $O(N \min(\log h, σ))$ time and uses $O(N)$ space, where $N$ is the maximum number of edges in the trie, $σ$ is the size of the alphabet, and $h$ is the height of the trie. For distinct palindromes, we develop several online algorithms based on different algorithmic frameworks, including approaches using the EERTREE (a.k.a. palindromic tree) and the suffix tree of a trie. These algorithms support leaf insertions and deletions in the trie and achieve different time and space trade-offs. Furthermore, as a by-product, we present online algorithms to construct the suffix tree and the EERTREE of the input trie, which is of independent interest. |
| title | Online Computation of Palindromes and Suffix Trees on Tries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.16485 |