2752 Seek the Name, Seek the Fame

問題概要

長さ40000以下の文字列が与えられる。
この文字のi番目までの部分文字列が元の文字列の接頭辞かつ接尾辞であるとき、そのようなiを全て昇順で出力せよ。

解法

rolling hashを使う。
rolling hashは文字列をk進数と見たときの値。
rolling hash一種類だと衝突がおこってWAだったので、二種類目のハッシュで検算してみたら通った。

ソースコード

int n; char in[400001];

int main()
{
	while(~scanf("%s",in))
	{
		n=strlen(in);
		ll h1=0,h2=0,t=1; int k=26;
		ll H1=0,H2=0,u=1; int l=29;
		bool f=1;
		rep(i,n)
		{
			h1*=k; h1+=in[i]-'a'; h2+=t*(in[n-1-i]-'a');
			H1*=l; H1+=in[i]-'a'; H2+=u*(in[n-1-i]-'a');
			if(h1==h2&&H1==H2)
			{
				if(!f)putchar(' '); else f=0;
				printf("%d",i+1);
			}
			t*=k; u*=l;
		}
		puts("");
	}
	return 0;
}