Distinct Substring Counts
MediumPractice library · +20 XPstringssuffix automatondata structures
Given a string S, find the total number of distinct substrings of S. A substring is a contiguous sequence of characters within a string. For example, the string "aba" has substrings "a", "b", "a", "ab", "ba", "aba". The distinct substrings are "a", "b", "ab", "ba", "aba", for a total of 5.
Input
A single line containing the string S.
Output
A single integer representing the total count of distinct substrings.
Constraints
1 <= |S| <= 200000
Time limit 2 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
aba
Output
5
Distinct substrings: 'a', 'b', 'ab', 'ba', 'aba'
Example 2
Input
aaaa
Output
4
Distinct substrings: 'a', 'aa', 'aaa', 'aaaa'
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
aba
Example 2 input
aaaa