[PKU1961]Period

求构成S[1..i]的最短重复子串重复次数。

和PKU2406一样，只不过将输出改成i/(i-p[i])而已。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cstdio>

const int MAXLEN(1000001);
char s[MAXLEN];
int data, len, p[MAXLEN];
int main()
{
  while (scanf("%d", &len), len != 0)
  {
    printf("Test case #%dn", ++data);
    scanf("%s", s);
    p[0] = -1;
    for (int i = 1, j = -1; i < len; ++i)
    {
      for (; j > -1 && s[j+1] != s[i]; j = p[j]);
      if (s[i] == s[j+1]) ++j;
      p[i] = j;
      int sublen = i-p[i];
      if ((i+1)%sublen == 0 && (i+1)/sublen > 1)
        printf("%d %dn", i+1, (i+1)/sublen);
    }
    printf("n");
  }
}

Comments