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

Автор Shivram, история, 7 лет назад, По-английски

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.

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

»
7 лет назад, # |
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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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); } }