POJ.2406 Power Strings

1.Problem
http://poj.org/problem?id=2406

2.Idea
KMP pre-processing

3.Source

 char s[1000006];  
 int n;  
 int nextarray[1000006];  
 void getnext()  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < n)  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int main()  
 {  
      while (scanf("%s", &s) > 0) {  
           n = strlen(s);  
           if (s[0] == '.' && n == 1) break;  
           getnext();  
           if (n % (n - nextarray[n]) == 0)  
                cout << n / (n - nextarray[n]) << endl;  
           else  
                cout << 1 << endl;  
      }  
      return 0;  
 }