poj-2406（字符串hash）

题目链接：传送门

思路：字符串hash，终止条件竟然判断错了，真是太大意了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1001000;
typedef unsigned long long ULL;
ULL power[maxn],a[maxn],b=13,tmp;
char str[maxn];
int main(void)
{
    int len,i,j,cnt,fg,ans;
    for(power[0]=1,i=1;i<maxn;i++) power[i]=power[i-1]*b;
    while(scanf("%s",str+1))
    {
        if(strcmp(str+1,".")==0) break;
        len=strlen(str+1);
        for(a[0]=0,i=1;i<=len;i++)  a[i]=a[i-1]*b+(ULL)str[i];
        for(i=1;i<=len;i++)
        {
            if(len%i) continue;
            tmp=a[i]-a[0]*power[i];
            for(j=0;j+i<=len&&a[j+i]-a[j]*power[i]==tmp;j+=i) ;
            if(j+i>len)
            {
                printf("%d
",len/i);
                break;
            }
        }
    }
    return 0;
}