> #include <stdio.h>
> #include <string.h>
> 
> const int MAX = 1000000+10;
> 
> char line[MAX];
> int n, nextval[MAX];
> 
> main() {
> //   freopen("10298.in", "r", stdin);
> //   freopen("10298.out", "w", stdout);
>    
>    while (gets(line) && strcmp(line, ".")) {
>       n = strlen(line);
>       memmove(line + 1, line, n);
>       
>       int i, pos;
>       pos = nextval[1] = 0;
>       for (i = 2; i <= n; i++) {
>          while (pos && line[pos + 1] != line[i])
>             pos = nextval[pos];
>          if (line[pos + 1] == line[i]) pos++;
>          nextval[i] = pos;
>       }
>       
>       int sub = n - nextval[n], ans;
>       if (n % sub == 0) ans = n / sub;
>       else ans = n;
>       
>       printf("%d\n", ans);
>    }
>    
>    return 0;         
> }   

• kmp (0) frkstyc 2005-10-30 20:35:45