Faster and simpler online computation of string net frequency

An occurrence of a repeated substring u in a string S is called a net occurrence if extending the occurrence to the left or to the right decreases the number of occurrences to 1. The net frequency ( NF ) of a repeated substring u in a string S is the number of net occurrences of u in S . Very recently, Guo et al. [SPIRE 2024] proposed an online O ( n log σ )-time algorithm that maintains a data structure of O ( n ) space which answers Single-NF queries in 𝑂 ⁢ ( 𝑚 ⁢ l o g ⁡ 𝜎 + 𝜎 2 ) time and reports all answers of the All-NF problem in O ( nσ 2 ) time. Here, n is the length of the input string S, m is the query pattern length, and σ is the alphabet size. The σ 2 term is a major drawback of their method since computing string net frequencies is originally motivated for Chinese language text processing where σ can be thousands large. This paper presents an improved online O ( n log σ )-time algorithm, which answers Single-NF queries in O ( m log σ ) time and reports all answers to the All-NF problem in output-optimal 𝑂 ⁡ ( ∣ 𝖭 𝖥 + ⁢ ( 𝑆 ) ∣ ) time, where 𝖭 𝖥 + ⁢ ( 𝑆 ) is the set of substrings of S paired with their positive NF values. We note that | 𝖭 𝖥 + ⁢ ( 𝑆 ) | = 𝑂 ⁡ ( 𝑛 ) always holds. In contrast to Guo et al.’s algorithm that is based on Ukkonen’s suffix tree construction, our algorithm is based on Weiner’s suffix tree construction.