Number of Distinct Substrings in a String
You are given a string s. Your task is to count the number of distinct substrings of s.
A substring is a contiguous sequence of characters taken from the original string. Two substrings are considered distinct if they differ in length or in character sequence at any position.
<svg xmlns="http://www.w3.org/2000/svg" width="200" height="45" viewBox="0 0 200 45"> <text x="10" y="20" font-family="monospace" font-size="15" fill="#222">s = " a b a "</text> <text x="28" y="38" font-family="monospace" font-size="11" fill="#666">0 1 2</text> </svg>For the string "aba" shown above, the distinct substrings are:
"a", "b", "ab", "ba", "aba" — a total of 5.
Substrings that appear from different positions (like "a" at indices 0 and 2) are counted only once.
Examples
Input: []
Output: 0
Input: ["a"]
Output: 0
Hints
Every substring is a **prefix of a suffix**. How can you use this relationship to ensure each distinct substring is discovered exactly once?
Substrings that share a common prefix correspond to the same path in the beginning. Think about a data structure that can **merge shared prefixes**.
Once all prefixes of all suffixes are inserted into a structure that deduplicates common beginnings, the number of distinct substrings equals the number of unique paths in that structure. How would you count them?
Related Problems
Number of Distinct Substrings in a String
You are given a string `s`. Your task is to count the number of **distinct** substrings of `s`.