< Previous
Next >
[Hash Table]
[String]
[Counting]
[Hash Function]
[Rolling Hash]
Hint 1
With the constraints, could we try every substring?
Hint 2
Yes, checking every substring has runtime O(n^2), which will pass.
Hint 3
How can we make sure we only count unique substrings?
Hint 4
Use a set to store previously counted substrings. Hashing a string s of length m takes O(m) time. Is there a fast way to compute the hash of s if we know the hash of s[0..m - 2]?
Hint 5
Use a rolling hash.