Блог пользователя daw_9

Автор daw_9, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится