1k_trash's blog

How to solve this string problem? Repeating substrings
By 1k_trash, 11 years ago, translation, In English

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 ac.

How to solve it? Thanks!

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

»
11 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    aclwawalaciac
    Your solution will give ac as an answer, but the correct answer is wa.
    It seems that you didn't notice "such substring that repeats one after another maximum number of times"

    → Reply