### Shivram's blog

By Shivram, history, 17 months ago, ,

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. 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?

Shivram

UPDATE: SOLVED

Method

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

•
• +5
•

 » 17 months ago, # | ← Rev. 2 →   +3 L is a period of the string if Z[L + 1] = N — L and N % L = 0. You are interested in the smallest L with these properties.
 » 17 months ago, # | ← Rev. 2 →   0 Find the first position j that j + z[j] = n and n % j = 0, so the answer will be j.
 » 17 months ago, # |   0 Auto comment: topic has been updated by ShivRam (previous revision, new revision, compare).
 » 17 months ago, # |   0 Auto comment: topic has been updated by ShivRam (previous revision, new revision, compare).
 » 17 months ago, # |   0 Auto comment: topic has been updated by ShivRam (previous revision, new revision, compare).
 » 12 months ago, # |   +5 This is the simplest method I found for similar problemhttps://open.kattis.com/problems/powerstrings #include char s[2000002]; main(){ int i,j,k,m,n; while (gets(s) && strcmp(s,".")) { m = n = strlen(s); for (i=2;i<=n;i++) { while (n%i == 0) { n /= i; for (j=0;j