Double-Ended Palindromic Trees in Linear Time
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918216396177408 |
|---|---|
| author | Wang, Qisheng Yang, Ming Zhu, Xinrui |
| author_facet | Wang, Qisheng Yang, Ming Zhu, Xinrui |
| contents | The palindromic tree (a.k.a. eertree) is a data structure that provides access to all palindromic substrings of a string. In this paper, we propose a dynamic version of eertree, called double-ended eertree, which supports online operations on the stored string, including double-ended queue operations, counting distinct palindromic substrings, and finding the longest palindromic prefix/suffix. At the heart of our construction, we identify a new class of substring occurrences, called surfaces, that are palindromic substring occurrences that are neither prefixes nor suffixes of any other palindromic substring occurrences, which is of independent interest. Surfaces characterize the link structure of all palindromic substrings in the eertree, thereby allowing a linear-time implementation of double-ended eertrees through a linear-time maintenance of surfaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_02292 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Double-Ended Palindromic Trees in Linear Time Wang, Qisheng Yang, Ming Zhu, Xinrui Data Structures and Algorithms Discrete Mathematics Information Retrieval The palindromic tree (a.k.a. eertree) is a data structure that provides access to all palindromic substrings of a string. In this paper, we propose a dynamic version of eertree, called double-ended eertree, which supports online operations on the stored string, including double-ended queue operations, counting distinct palindromic substrings, and finding the longest palindromic prefix/suffix. At the heart of our construction, we identify a new class of substring occurrences, called surfaces, that are palindromic substring occurrences that are neither prefixes nor suffixes of any other palindromic substring occurrences, which is of independent interest. Surfaces characterize the link structure of all palindromic substrings in the eertree, thereby allowing a linear-time implementation of double-ended eertrees through a linear-time maintenance of surfaces. |
| title | Double-Ended Palindromic Trees in Linear Time |
| topic | Data Structures and Algorithms Discrete Mathematics Information Retrieval |
| url | https://arxiv.org/abs/2210.02292 |