Please subscribe to the official Codeforces channel in Telegram via the link ×

Shivram's blog

By Shivram, history, 7 years ago, In English

Hello guys,

Is there any way to find the shortest period of a string using Z algorithm. I know of one using KMP.


Sorry for stating the question wrongly.

I was solving this. So the point where i got struck was: given a string, find shortest period for each prefix. Can this be solved by Z-algorithm in linear time? And also is there a way to transform Z array to LPS array and vice-versa?

Thanks in advance,




This converts Z to LPS. After that we can use the editorial method.

Full text and comments »

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