I believe what the analysis means is that Given a sub-string in the larger string, finding the matching words in dictionary takes almost O(1). You don't need to go through all the words in dictionary, just the ones with same length, same starting, same ending letters and same frequency array in the middle.
Pedro Osório <[email protected]>于2018年3月22日周四 下午3:32写道： > 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. > -- 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/CAGDEU-LzEvBFfL_bO50zUPHdZQqz%2Bxs8EULceriYaKXLDw7dZQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
