Counting Distinct (Non-)crossing Substrings

Haruki Umezaki

doi:10.1007/978-3-032-05228-5_22

Counting Distinct (Non-)crossing Substrings

2026-01-01

0

PRE

AI

DOI：10.1007/978-3-032-05228-5_22

Original

Original request for help

Save

Abstract

En 中文

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 position k in w, and thus a direct application would require O(n(2)) timefor all positions k = 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.

Keywords:

string algorithms ,distinct substrings

runs

LPF arrays

Counting Distinct (Non-)crossing Substrings

Abstract

Journal

Organization