Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912049954553856 |
|---|---|
| author | Mieno, Takuya Takahashi, Shun Seto, Kazuhisa Horiyama, Takashi |
| author_facet | Mieno, Takuya Takahashi, Shun Seto, Kazuhisa Horiyama, Takashi |
| contents | A string is said to be closed if its length is one, or if it has a non-empty factor that occurs both as a prefix and as a suffix of the string, but does not occur elsewhere. The notion of closed words was introduced by [Fici, WORDS 2011]. Recently, the maximum number of distinct closed factors occurring in a string was investigated by [Parshina and Puzynina, Theor. Comput. Sci. 2024], and an asymptotic tight bound was proved. In this paper, we propose two algorithms to count the distinct closed factors in a string T of length n over an alphabet of size σ. The first algorithm runs in O(n log σ) time using O(n) space for string T given in an online manner. The second algorithm runs in O(n) time using O(n) space for string T given in an offline manner. Both algorithms utilize suffix trees for sliding windows. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_19576 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees Mieno, Takuya Takahashi, Shun Seto, Kazuhisa Horiyama, Takashi Data Structures and Algorithms A string is said to be closed if its length is one, or if it has a non-empty factor that occurs both as a prefix and as a suffix of the string, but does not occur elsewhere. The notion of closed words was introduced by [Fici, WORDS 2011]. Recently, the maximum number of distinct closed factors occurring in a string was investigated by [Parshina and Puzynina, Theor. Comput. Sci. 2024], and an asymptotic tight bound was proved. In this paper, we propose two algorithms to count the distinct closed factors in a string T of length n over an alphabet of size σ. The first algorithm runs in O(n log σ) time using O(n) space for string T given in an online manner. The second algorithm runs in O(n) time using O(n) space for string T given in an offline manner. Both algorithms utilize suffix trees for sliding windows. |
| title | Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.19576 |