Chen_ChaoRui's blog

By Chen_ChaoRui, 6 years ago, In English,

As we know, during the contest CodeForces Round #189 Codeforces Round #189 (Div. 1) few participators solved problem 319D. 319D - Have You Ever Heard About the Word?

And almost all of the algorithms they used are brute force. At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. Just like these: C++ 3951251 Pascal 3957673

But I thought this problem as for D was authored for some algorithms more difficult like Suffix Automaton or Suffix Arrays. Like this: 3952463

The complexity of these algorithms are better than brute force, but they caused more time when they are using. I think the 6 seconds time limit was for this.

Also we may solve this problem using Hash. It is a very good algorithm for problems about strings. It is easier than suffix algorithms and its complexity can be great. Like this: 3958099

Maybe we can make some testdatas to let brute force gets Time Limit Exceeded. Sorry for my poor English. After all, thanks for the problem authors, Round #189 was a good contest.

 
 
 
 
  • Vote: I like it
  • +64
  • Vote: I do not like it