POJ 2406 Power Strings (KMP)

对于这道题，考的就是KMP算法中对于子串的自匹配模式的考察。具体的KMP算法可参看KMP算法详解，主要看对B串的处理。

这题给出一个比较特殊的测试数据供大家参考

aabaaaba

结果应该为2

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 void result(char str[1000001])
 5 {
 6   int i;
 7   int j;
 8   int len = strlen(str);
 9   int p[1000001];
10   p[0] = -1;
11   for (i = 1; i < len; i++)
12   {
13     j = p[i-1];
14     while (str[i] != str[j+1] && j > -1)
15     {
16       j = p[j];
17     }
18     if (str[i] == str[j+1])
19       p[i] = j + 1;
20     else
21       p[i] = j;
22   }
23   int count = len - 1 - p[len-1];
24   if ((p[len - 1] + 1) % count == 0)
25     printf("%d\n", (p[len - 1] + 1) / count + 1);
26   else
27     printf("%d\n", 1);
28 }
29 
30 int main()
31 {
32   char str[1000001];
33   while (scanf("%s", str) != EOF)
34   {
35     if (str[0] == '.')
36       break;
37     result(str);
38   }
39   //printf("\n");
40   return 0;
41 }