happystone

niuniu

pku 2406

 

 1#include<iostream>
 2using namespace std;
 3#include "string.h"
 4#define MAX 1000000
 5char s[MAX];    
 6int next[MAX];
 7int main()
 8
 9{
10    //freopen("1.txt","r",stdin);
11    int i, j, len;
12    while (scanf("%s",&s) != EOF)
13    {
14        if (s[0] == '.' && s[1] == '\0')
15        {
16            break;
17        }
18        len = strlen(s);
19        i = 0;
20        j = -1;
21        next[0] = -1;
22        while (i < len)
23        {
24            if (j == -1 || s[i] == s[j])
25            {
26                ++i;
27                ++j;
28                if (s[i] != s[j])
29                {
30                    next[i] = j;
31                }
32                else
33                {
34                    next[i] = next[j];
35                }
36            }
37            else
38            {
39                          j = next[j];
40            }
41        }
42        i -= j;
43        if (len % i == 0)
44        {
45            i = len / i;
46        }
47        else
48        {
49           i = 1;
50        }
51        printf("%d\n", i);
52    }
53     system("pause");
54    return 0;
55}
56
57

posted on 2010-08-09 15:56 玉中石 阅读(151) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理