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.