Counting distinct (non-)crossing substrings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916814637760512 |
|---|---|
| author | Umezaki, Haruki Shibata, Hiroki Köppl, Dominik Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo |
| author_facet | Umezaki, Haruki Shibata, Hiroki Köppl, Dominik Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo |
| contents | Let $w$ be a string of length $n$. The problem of counting factors crossing a position - Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Leqroc, and Rytter, 2021], asks to count the number $\mathcal{C}(w,k)$ (resp. $\mathcal{N}(w,k)$) of distinct substrings in $w$ that have occurrences containing (resp. not containing) a position $k$ in $w$. The solutions provided in their textbook compute $\mathcal{C}(w,k)$ and $\mathcal{N}(w,k)$ in $O(n)$ time for a single position $k$ in $w$, and thus a direct application would require $O(n^2)$ time for all positions $k = 1, \ldots, n$ in $w$. Their solution is designed for constant-size alphabets. In this paper, we present new algorithms which compute $\mathcal{C}(w,k)$ in $O(n)$ total time for general ordered alphabets, and $\mathcal{N}(w,k)$ in $O(n)$ total time for linearly sortable alphabets, for all positions $k = 1, \ldots, n$ in $w$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22728 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting distinct (non-)crossing substrings Umezaki, Haruki Shibata, Hiroki Köppl, Dominik Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Data Structures and Algorithms Let $w$ be a string of length $n$. The problem of counting factors crossing a position - Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Leqroc, and Rytter, 2021], asks to count the number $\mathcal{C}(w,k)$ (resp. $\mathcal{N}(w,k)$) of distinct substrings in $w$ that have occurrences containing (resp. not containing) a position $k$ in $w$. The solutions provided in their textbook compute $\mathcal{C}(w,k)$ and $\mathcal{N}(w,k)$ in $O(n)$ time for a single position $k$ in $w$, and thus a direct application would require $O(n^2)$ time for all positions $k = 1, \ldots, n$ in $w$. Their solution is designed for constant-size alphabets. In this paper, we present new algorithms which compute $\mathcal{C}(w,k)$ in $O(n)$ total time for general ordered alphabets, and $\mathcal{N}(w,k)$ in $O(n)$ total time for linearly sortable alphabets, for all positions $k = 1, \ldots, n$ in $w$. |
| title | Counting distinct (non-)crossing substrings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.22728 |