help me with string problem.

Revision en1, by Yasuho_Hirose, 2022-03-05 00:52:48

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/

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Yasuho_Hirose 2022-03-05 00:52:48 501 Initial revision (published)