10234 - Frequent Substrings

[angga888]

I haven't understood well if I should print the most frequent substring as lowercase substring, or just the most frequent substring found in it's least lexicographically way ...

Just ouput the most frequent substring as lowercase substring.

So for your input, my AC code outputs:

Code: Select all

3 abc

Hope it helps

[chuzpa]

thanks! I got Accepted ! :D:D:D:D

[FAQ]

I still got MLE (not TLE) at ~6s
Could anyone help me some ideas to optimize it please? I tried map <string, int>

[Jan]

Suppose you are given a string of length 1000. And the query contains 1-1000. Then your code will return nothing but MLE. So, clear your map after each query. I used manual hashing and got it Accepted.
Hope these help.

[helloneo]

I still got MLE (not TLE) at ~6s
Could anyone help me some ideas to optimize it please? I tried map <string, int>

I also used map<string, int> and got AC..
I clear map everytime start a query..
It takes over 7 secs though..

[Abednego]

Could somebody please post an AC output for this case?

Code: Select all

In theory, there is no difference between theory and practice, but in practice, there is.
2
4
9
In theory, there is no difference between theory and practice, but in practice, there is.
2
4
9

I can't get rid of the PE.

[Jan]

My accepted code returns...

Output:

Code: Select all

4  the
2  practice
4  the
2  practice

Hope it helps.

[fh]

I always got PE for this problem...

what is the output for this:

Code: Select all

In theory, there is no difference between theory and practice, but in practice, there is.
2
4
9
                             
2
4
9
In theory, there is no difference between theory and practice, but in practice, there is.
2
4
9

[Jan]

My accepted code returns

Output:

Code: Select all

4  the
2  practice
26     
21          
4  the
2  practice

Hope it helps.

[stcheung]

Regarding the capitalization, all you have to do is to convert the input string to lowercase right at the beginning. In other words, the ngram outputs will all be lowercase. Regarding MLE above with C++, I guess that demonstrates the convenience of Java's GC. This problem is so extremely straightforward with language like Java that I feel like I am cheating here. My Java solution was like <30 lines if we ignore the IO helper methods. So my point is, if you didn't get AC with C++ STL, but you really want to get it over with, then just try Java. It will take you less than 10 min, or 5 min if you type fast.

[DD]

With the support of unordered_map, it is still possible to solve this problem by C++ STL. Just like other people said, this is a really straight forward problem. Good Luck