Funcia
Lv.4lcp-arraystringsuffix-array

Number of Distinct Substrings

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given a string s of lowercase English letters, return the number of distinct non-empty substrings of s (contiguous; a substring that occurs in several places is counted once).

Examples

sresult
"abab"7
"aaa"3
"banana"15

Example 1 — a, b, ab, ba, aba, bab, abab.

Example 2 — a, aa, aaa.

Example 3 — 21 substring positions, 15 distinct contents.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(s: string) → long

Constraints

  • 1≤N=1 \le N = s.length ≤200,000\le 200{,}000
  • s consists of lowercase English letters only.
  • The answer may not fit in 32 bits.

Expected complexity

Time
O(N log^2 N)
Space
O(N)

Examples

sExpected
"abab"7
"aaa"3
"banana"15

Hint

Hint

Every substring is a prefix of some suffix, so the answer is N(N+1)/2N(N+1)/2 minus the overlaps between lexicographically adjacent suffixes: build the suffix array (prefix doubling, O(Nlog⁡2N)O(N \log^2 N) or O(Nlog⁡N)O(N \log N) with radix sort), compute the LCP array with Kasai's algorithm in O(N)O(N), and subtract ∑lcp\sum \text{lcp}. A suffix automaton also works. Comparing suffixes as strings, or putting substrings in a set, is quadratic on repetitive strings like aaaa… and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)204 msestimated
C++ (GCC, gnu++23)204 msderived
Python 3.131832 msderived
Java 251388 msderived
Kotlin 2.4 (JVM)1408 msestimated
C# 14 (.NET 10)1408 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.