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 to solve this problem is quite comfortable.
- Create a
- 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