Problem Statement
Explain how to count all distinct substrings of a string efficiently.
Explanation
Naively, generating all substrings takes O(n²) and checking uniqueness takes extra time. Efficient methods use suffix trees or suffix arrays with LCP (Longest Common Prefix) array. The number of distinct substrings equals n*(n+1)/2 minus the sum of LCP values. Time complexity: O(n log n) for suffix array method.
Code Solution
SolutionRead Only
// Distinct substrings = n*(n+1)/2 - sum(LCP) // Example: s = 'aba' // Suffixes: a, aba, ba // Sorted: a, aba, ba // LCP = [1,0] => sum=1 // Distinct substrings = 3*(4)/2 - 1 = 5 // Substrings: a, ab, aba, b, ba
Practice Sets
This question appears in the following practice sets:
