文字列ハッシュ-POJ-2406文字列のサイクル
10705 ワード
タイトルリンク:http://poj.org/problem?id=2406もしa=“123”ならば、a^2=“123123”、a^3=12323123
今文字列a^nをあげて、最小のnがいくらなのかを確定させますか?
構想:文字列長nの因数を列挙し、各ハッシュ値が等しいかどうかを暴力する.
今文字列a^nをあげて、最小のnがいくらなのかを確定させますか?
構想:文字列長nの因数を列挙し、各ハッシュ値が等しいかどうかを暴力する.
#include
using namespace std;
#define ull unsigned long long
const int maxn=1000005;
ull base =131;
char s[1000005];
ull g[1000005];
ull p[1000005];
ull Hash(char s[])
{
int len=strlen(s);
ull ans=0;
g[0]=s[0];
for(int i=1;i<len;i++)
{
g[i]=g[i-1]*base+s[i];
}
return g[len-1];
}
void getp()
{
p[0]=1;
for(int i=1;i<=maxn;i++)
{
p[i]=p[i-1]*base;
}
}
ull getLR(int l, int r)// T l - r hash
{
if(l==0)
{
return g[r];
}
return g[r]-g[l-1]*p[r-l+1];
}
int main()
{
while(~scanf("%s",s), s[0]!='.')
{
Hash(s);
getp();
int Len=strlen(s), f=1;
for(int i=1;i<=Len;i++)
{
if(Len%i==0)
{
if(getLR(i, Len-1)==getLR(0, Len-i-1))
{
f=i;
break;
}
}
}
printf("%d
",Len/f);
}
return 0;
}