Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |