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

Shortest period of a string
Автор 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);
   }
}
→ Ответить