Shortest period of a string
Difference between en3 and en4, changed 157 character(s)
Hello guys,↵
↵
Is there any way to find the shortest period of a string using Z algorithm. I know of one using KMP. ↵
↵
EDIT:↵
↵
Sorry for stating the question wrongly.↵
↵
I was solving [this](http://mirror.codeforces.com/contest/825/problem/F). 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,↵
↵
Shivram↵
↵
↵
UPDATE: SOLVED↵
↵
[Method](http://mirror.codeforces.com/blog/entry/3107?#comment-83420)↵
↵
This converts Z to LPS. After that we can use the editorial method.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Shivram 2017-08-15 14:15:04 157
en3 English Shivram 2017-08-15 13:46:18 15 Tiny change: '-algorithm? And also' -> '-algorithm in linear time? And also'
en2 English Shivram 2017-08-15 13:45:40 325
en1 English Shivram 2017-08-15 12:57:23 178 Initial revision (published)