ShivRam's blog

By ShivRam, history, 14 months 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.

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?

Thanks in advance,

Shivram

UPDATE: SOLVED

Method

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

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

»
14 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Find the first position j that j + z[j] = n and n % j = 0, so the answer will be j.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ShivRam (previous revision, new revision, compare).

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ShivRam (previous revision, new revision, compare).

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ShivRam (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

This is the simplest method I found for similar problem

https://open.kattis.com/problems/powerstrings


#include <stdio.h> 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<m-m/i && s[j] == s[j+m/i];j++); if (j == m-m/i) m /= i; } } printf("%d\n",strlen(s)/m); } }