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.

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 165 |

3 | antontrygubO_o | 165 |

3 | Vovuh | 165 |

6 | tourist | 162 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

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.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2019 13:39:49 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

Problem link: http://acm.timus.ru/problem.aspx?space=1&num=1590

another possible solution: https://www.geeksforgeeks.org/count-distinct-substrings-string-using-suffix-array/

here is the problem link

and here is the solution by me.

I know that there is a solution in O (N log N) with Suffix Array and LCP, but the real question is the maximum value that the F () function could reach in any string of at most 100,000 characters with a 26 letter dictionary.

I think that the more characters the string has, the less possibility there is that the function F () defined for every string of at most 100000 and with a 26-letter dictionary reaches its maximum value but I am not sure of the maximum value of the function F (). Which would suit me very well because I think I solve many problems depending on the maximum value of F ().

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).