1200 Crazy Search
問題概要
文字列が与えられる。この文字列の連続する部分文字列で、長さがnのものはいくつあるか求めよ。文字列の文字の数はncで、部分文字列の数は1600万を超えない。
解法
rolling hashを使う。
rolling hashの計算方法は何度も書いたので省略。
部分文字列は16M個しか出てこないことが保証されているため、hashの値は0〜16Mを取る。
したがって、長さ16Mの配列を取れば全く衝突がおきずに文字列が出現したかの判定ができる。
ソースコード
const int MX=16000000; char in[MX],d[256]; int n,m,l; bool hash[MX]; int main(){ scanf("%d%d ",&n,&m); gets(in); rep(i,256)d[i]=-1; m=0; for(int i=0;in[i];i++,l++)if(d[in[i]]==-1)d[in[i]]=m++; if(l<n){ puts("0"); return 0; } int i=0,h=0,ans=1,t=1; rep(i,n-1)t*=m; for(;i<n;i++)h*=m,h+=d[in[i]]; hash[h]=1; for(;i<l;i++){ h-=t*d[in[i-n]]; h*=m; h+=d[in[i]]; if(!hash[h])hash[h]=1,ans++; } printf("%d\n",ans); return 0; }