daw_9's blog

By daw_9, 11 years ago, In English

Hi. I'm attempting to solve this problem: http://main.edu.pl/en/archive/pa/2011/naj (it belongs to the competition 'Algorithmic Engagements 2011')

Summary: Given a long string find the length of the shortest period of the resulting string after removing a single character (A string t is a period of s iff s is a preffix of tk for some k)

I can't see a way faster than O(N^2) (based on KMP). Could you give me a hint for a faster solution ?

Regards.

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