The analysis presented here mentions an approach that would take O(N sqrt(M)) for the large case: https://code.google.com/codejam/contest/9234486/dashboard#s=a&a=2
However, the approach that is described (as far as I understand it) still compares the 26 frequency counts for every word in the dictionary at each position in the larger string: "for each such length, we perform the same process as above, checking against only the dictionary words with that length" This would still be O(N*L) - or O(N*L*K) if we decide to consider the size of the alphabet K=26 in the analysis. What am I missing? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/37d8693f-e33d-4611-8b1a-84a34de8cb03%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
