pku2406.cpp

来自「内有KMP的模板和pku2406」· C++ 代码 · 共 38 行

//////POJ2406 Power Strings
////KMP

#include <stdio.h>
#include <string.h>

const int MAX = 1000000+10;

char line[MAX];
int n, nextval[MAX];

int main() {
//   freopen("10298.in", "r", stdin);
//   freopen("10298.out", "w", stdout);
   
   while (scanf("%s",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 = 1;
      
      printf("%d\n", ans);
   }
   
   return 0;         
}