You are given a string (|S| <= 10^5) and have to find such substring that repeats one after another maximum number of times. Or, if there are some such substrings, you must choose the longest/shortest/lexicografically_something.
For example: for test
bacacacb answer is
How to solve it? Thanks!
Make a suffix array, and an LCP array. Now your task is to find the longest non-zero contiguous subsequence in the LCP array, which can easily be done in linear time.
edit: sorry, I thought it just said maximum number of occurrences.
Your solution will give
acas an answer, but the correct answer is
It seems that you didn't notice "such substring that repeats one after another maximum number of times"