[JZOJ 5462] 好文章 {双重hash}

---

题目

Description

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

Input

第一行包含两个整数?,?，表示文章的长度和需要统计的子串长度。
第二行包含一个长度为?的只包含小写字母的字符串。

Output

输出一行一个整数，表示文章的评分。

---

结题思路

这道题可以用哈希做，可以因为数据有些刁钻（哈希表竟然碰撞了）。
对于此：

• 可以将模数开大（听说自然溢出会被卡）
• 也可以用双重hash表 ----->>> 然后把所有hash值扔到set<make_pair<> >里 ----->>> 输出 $s.size()$s.size()即可

---

代码

#include<cstdio>
#include<set>
#define ll long long
#define rr register 
using namespace std;
const int cnt=200001; 
const ll xx=15312137,yy=3113791,modx=1e9+7,mody=1e9+9;
int n,m; ll a[cnt],b[cnt],ans=0,bns=0;
char c[cnt]; 
set<pair<ll,ll> >s; 
inline int read()
{
int p=0; char q=getchar(); 
while (q<'0'||q>'9') q=getchar(); 
while (q>='0'&&q<='9') p=(p<<3)+(p<<1)+q-'0',q=getchar(); 
return p; 
}
int main()
{
n=read(),m=read(); 
a[0]=b[0]=1; 
for (rr int i=1;i<=n;i++)
 a[i]=(a[i-1]*xx)%modx,b[i]=(b[i-1]*yy)%mody; 
scanf("%s",c+1); 
for (rr int i=1;i<=m;i++)
{
ans=(ans+(a[m-i]*c[i])%modx)%modx;
bns=(bns+(b[m-i]*c[i])%mody)%mody; 	
}
s.insert(make_pair(ans,bns)); 
for (rr int i=m+1;i<=n;i++)
 {
 	ans=(ans-a[m-1]*c[i-m]%modx+modx)%modx; 
 	ans=(ans*xx)%modx; ans=(ans+c[i])%modx; 
 	bns=(bns-b[m-1]*c[i-m]%mody+mody)%mody; 
 	bns=(bns*yy)%mody; bns=(bns+c[i])%mody; 
 	s.insert(make_pair(ans,bns)); 
 }
printf("%d",s.size()); 
}