「FZOJ2034」好文章

题意：nodgd 写了一篇文章，自认为这是一篇好文章。nodgd 的文章由 $n$ 个小文字母组成。文章的一个子串指的是文章中的一段连续的字母，子串的长度这一段的字母个数。nodgd 在文章中用了排比、对偶、前后照应之类的手法以就有很多个子串是相同或者相近的。为了向大家证明这是一篇好文章，决定给自己的文章进行评分。nodgd 首先确定了一个整数 $m$，然后统计出文有多少个不相同的长度为 $m$ 的子串，这个数量就是文章的评分。然而，nodgd 懒得老老实实计算这个评分了，就把任务丢给了你。

一道经典的 hash 题(避免忘记还是写一篇把)。

用双 hash 将 hash 值算出来，然后排个序，顺次比较相邻 hash 值是否相等，不等则统计答案。

注意由于长度 $m$ 确定，可以直接用快速幂算一段长度用到的值(我也不知道叫什么名字，反正就是代码中的 b1,b2)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
char s[201010];
long long mod1=1e9+7,mod2=1e9+9,ans;
long long b1,b2;
struct node
{
	long long q1,q2;
	long long h1,h2;
}h[201010];
long long power(long long a,long long b,long long p)
{
	long long ans=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			ans=ans*a%p;
		a=a*a%p;
	}
	return ans%p;
}
void Hash(int l,int r)
{
	h[0].h1=1;
	h[0].h2=1;
	long long seed1=31;
	long long seed2=37;
	for(int i=l;i<=r;i++)
	{
		h[i].h1=(h[i-1].h1%mod1*seed1%mod1+(s[i]-'a'+1)%mod1)%mod1;
		h[i].h2=(h[i-1].h2%mod2*seed2%mod2+(s[i]-'a'+1)%mod2)%mod2;
	}
}
long long cmp(node a,node b)
{
	if(a.q1==b.q1)
		return a.q2<b.q2;
	return a.q1<b.q1;
}
int main()
{
	scanf("%d%d\n",&n,&m);
	scanf("%s",s+1);
	Hash(1,n);
	b1=power(31,m,mod1);
	b2=power(37,m,mod2);
	for(int i=1;i<=n-m+1;i++)
	{
		h[i].q1=(h[i+m-1].h1%mod1-(h[i-1].h1%mod1*b1%mod1)+mod1)%mod1;
		h[i].q2=(h[i+m-1].h2%mod2-(h[i-1].h2%mod2*b2%mod2)+mod2)%mod2;
	}
	sort(h+1,h+n-m+2,cmp);
	for(int i=1;i<=n-m+1;i++)
	{
		if(h[i].q1==h[i-1].q1&&h[i].q2==h[i-1].q2)
			continue;
		ans++;
	}
	printf("%lld",ans);
	return 0;
}