TY - GEN
T1 - Counting Distinct (Non-)crossing Substrings
AU - Umezaki, Haruki
AU - Shibata, Hiroki
AU - Köppl, Dominik
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
PY - 2026
Y1 - 2026
N2 - 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 C(w,k) (resp. 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 C(w,k) and N(w,k) in O(n) time for a single positionk in w, and thus a direct application would require O(n2) time for all positionsk=1,…,n in w. Their solution is designed for constant-size alphabets. In this paper, we present new algorithms which compute C(w,k) in O(n) total time for general ordered alphabets, and N(w,k) in O(n) total time for linearly sortable alphabets, for all positions k=1,…,n in w.
AB - 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 C(w,k) (resp. 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 C(w,k) and N(w,k) in O(n) time for a single positionk in w, and thus a direct application would require O(n2) time for all positionsk=1,…,n in w. Their solution is designed for constant-size alphabets. In this paper, we present new algorithms which compute C(w,k) in O(n) total time for general ordered alphabets, and N(w,k) in O(n) total time for linearly sortable alphabets, for all positions k=1,…,n in w.
KW - LPF arrays
KW - distinct substrings
KW - runs
KW - string algorithms
UR - https://www.scopus.com/pages/publications/105017377312
UR - https://www.scopus.com/pages/publications/105017377312#tab=citedBy
U2 - 10.1007/978-3-032-05228-5_22
DO - 10.1007/978-3-032-05228-5_22
M3 - Conference contribution
AN - SCOPUS:105017377312
SN - 9783032052278
T3 - Lecture Notes in Computer Science
SP - 281
EP - 290
BT - String Processing and Information Retrieval - 32nd International Symposium, SPIRE 2025, Proceedings
A2 - Badkobeh, Golnaz
A2 - Radoszewski, Jakub
A2 - Tonellotto, Nicola
A2 - Baeza-Yates, Ricardo
A2 - Baeza-Yates, Ricardo
A2 - Baeza-Yates, Ricardo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 32nd International Symposium on String Processing and Information Retrieval, SPIRE 2025
Y2 - 8 September 2025 through 11 September 2025
ER -