1 // kmp算法

2 #include " iostream "

3 using namespace std;

4 char s[ 10000001 ];

5 int next[ 100001 ];

6 int L;

7 int i,j;

8 void Index_kmp()

9 {

10 while (i < L) // kmp核心算法

11 {

12 if (j == 0 || s[i] == s[j]) // 继续比较后继字符

13 { ++ i; ++ j; next[i] = j; }

14 else

15 j = next[j]; // 串向右移动

16 }

17 }

18 int main()

19 {

20 while ( 1 )

21 {

22 scanf( " %s " ,s);

23 if (s[ 0 ] == ' . ' ) break ;

24 L = strlen(s);

25 i = 1 ; j = 0 ; next[ 0 ] = 0 ;

26

27 Index_kmp();

28 if (L % (L - next[L]) == 0 ) printf( " %d\n " ,L / (L - next[L])); // 形成周期性

29 else printf( " 1\n " );

30 }

31 return 0 ;

32 }