[PKU2406]Power Strings

求构成原串的最短重复子串长度。

KMP的预处理部分即可解决。预处理完，p[len]表示当len匹配失败的时候的回退位置，也就是说p[len]+1..len这部分是构成原串的一个重复子串，子串的长度也就是len-p[len]。题目求的是最多的重复次数，相当于求最短的重复子串，因此答案就是len/(len-p[len])。不过有个特殊点要判断，那就是如果len mod (len-p[len]) != 0，那么原串肯定不是由p[len]+1..len构成的，也肯定不是由任意重复子串连接构成的，因此此时的答案就是1。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <cstdio>
#include <cstring>

const int MAXLEN(10000001);
char s[MAXLEN];
int p[MAXLEN];
int main()
{
  while (scanf("%s", s), s[0] != '.')
  {
    p[0] = -1;
    int len = strlen(s);
    for (int i = 0, j = -1; i < len-1; ++i)
    {
      for (; j > -1 && s[j+1] != s[i+1]; j = p[j]);
      if (s[j+1] == s[i+1]) ++j;
      p[i+1] = j;
    }
    int sublen = len-1-p[len-1];
    if (len % sublen)
      printf("%dn", 1);
    else
      printf("%dn", len/sublen);
  }
}

Comments