Hello everybody. I took part in Codeforces Round #166 (Div. 2) last night. I'm a newbie, so I only solved Problem ABD.

Last night, I thought that enumerating substrings and using `set<string>`

in C++ could solve this problem in `O(n^2logn)`

, and seems code length would be quite short. Then I coded it (only 32 lines) and submitted it. Unfortunately, I forgot to calculate the memory (needs 1G memory), and MLE: 3097364

Then I thought I should change map to hash, but actually, I don't know how to hash it. However, fortunately, I thought of a tiny&powerful data structure: `Trie`

!

Using `Trie`

to solve this problem is quite comfortable.

- Create a
`root`

node. - Enumerate the start point of the substring in the string. Then enumerate the end of the substring. And at the same time, travel the
`Trie`

. If current node is valid and not marked in`Trie`

, ++ans!

Quite easy to code (also 32 lines), and the memory cost is quite low, runs fast, too: 3098298 3105955 I've read the official tutorial & many other people's submissions. I found this problem could be solve by `Suffix Array`

, `RK Hash`

, ... I learnt a lot from all you guys, especially Robert's RK hash: 3106330

Thanks Codeforces for providing such a good place to learn from each other.

Your first algo is having a hidden cost of O(n). Hence it is O((n^3) * log(n)) .

Basically you are describing the author's solution. If you read carefully they state their structure as a trie. It's true your code is shorter, but some people will write with the same speed a little bit longer solution, but well structured. Anyways, this was a nice problem :)

Can KMP alorithm be used to solve it?