### jmrh_1's blog

By jmrh_1, history, 6 weeks ago, , Hello codeforces Let's say an F(string s) as the number of different substrings that s has. Which is the maximum F(string x) such that x at most has 100000 characters and a dictionary of 26 characters. Comments (13)
 » 6 weeks ago, # | ← Rev. 2 →   Number of total substrings of a string of length n is n * (n + 1) / 2
•  » » That's not the number of distinct subtrings, that's the number of total substrings.
 » Is there a problem link
 » https://cp-algorithms.com/string/string-hashing.html in this tutorial you can learn how to find the number of distinct substrings using hashing.
•  » » It's complexity is O(N^2).
 » To solve this you can build a suffix tree of the original string S and count the amount of nodes on the tree. The complexity of this solution is O(N) if you use Ukkonen's algorithm to build the suffix tree.
 » 3 weeks ago, # | ← Rev. 2 →   I wrote the Suffix Array solution, and generated a few random strings of length 100.000.The maximal value of the number of substrings is N * (N - 1) / 2 = 5000050000, and all the random strings i generated had around 4999700000 distinct substrings. It's almost 0.99995% of the maximal value we could get.If we think about it it's quite obvious why: as the string is random, there is virtually no chance that two different substrings of length >= 10 match (the probability of a colision is 1/26^10 = 7e-15 ~= 0). So except for the small substrings of length 1, 2, ... 9 (which are 9 * N = 900000), all the remaining 4999500000 are distinct.So if your hope was that there are few such distinct substrings, sorry to break it down :(
•  » » Moreover, there's an obvious statement that there're no more than $26$ distinct substrings of size 1, $26^2$ of size 2 and $26^3$ of size 3. N * (N - 1) // 2 - (N - 26) - (N - 1 - 26 * 26) - (N - 2 - 26 * 26 * 26) equals 4999668281. You get almost that (if not exactly).