首页 > 代码库 > (Power Strings)sdutoj2475

(Power Strings)sdutoj2475

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char a[1000001];
int next[1000001];
int l;
void Getnext()
{
  int j=-1;
  int i=0;
  next[0]=-1;//忘写了,死循环
  while(i<l)
  {
    if(j==-1||a[i]==a[j])
    {
      i++;
      j++;
      next[i]=j;
    }
    else j=next[j];
  }

}
int main()
{
    while(scanf("%s",a)!=EOF)
    {
      if(strcmp(a,".")==0) break;
      l=strlen(a);
      Getnext();
      if(l%(l-next[l])==0)
      {
        printf("%d\n",l/(l-next[l]));
      }
      else
      printf("1\n");
    }

    return 0;
}