Yasuho_Hirose's blog

By Yasuho_Hirose, history, 3 years ago, In English

give a string, count how many repeating substring in this string, in another words, count substring appear >=2 times, and characters of substring can overlap. n<=1e5 Example: aaaaa, answer is 4, substrings are: a,aa,aaa,aaaa. aabaab, answer is 5, substrings are: a,b,aa,ab,aab. I only can solve it with O(n^2) solution and of course, it gives TLE. How to solve it in < O(n^2) time complexity? You can submit in here: https://www.spoj.com/PTIT/submit/PTIT015J/

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

It should be possible to solve directly using the suffix tree and probably also the equivalent suffix structures.