小可可是学校图书馆的管理员，现在他接手了一个十分棘手的任务。由于学校需要一些材料，校长需要在文章中检
索一些信息。校长一共给了小可可N篇文章，每篇文章为一个字符串。现在，校长需要他找到这样的单词，它至少
在这N篇文章中的M篇文章里出现过，且单词长度为L。可是，工作量十分庞大，但校长又急需小可可完成这项任务
。现在他向你求助，需要你编写程序完成这项艰巨的任务
Input
第1行3个正整数N，M，L，表示文章的数目，单词至少出现在M篇文章中和每个单词的长度。
接下来N行，每行一个字符串，表示一篇文章。
1≤N,M≤2000，L≤1000。每篇文章长度不大于1000，均有小写字母组成
Output
仅一行，表示满足检索条件的单词数。
Sample Input
3 2 2
noip
istudycpp
imacppstudent
Sample Output
5
//这5个单词分别为：st，tu，ud，pp，cp。
Sol:对于一些数据精心构造过的，最好写成双hash
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long LL;
const int MaxN=2005;
const int MaxM=1000005;
const int MinMod=999973;
const LL MaxMod=499999999999993ll;
struct Node
{
int no,cnt;//no为单词所在文章编号,cnt为单词出现的次数
LL s;//s为单词的hashh值
int next;//用开散列解决冲突
}h[MaxM];
int N,M,L,tot,ans;
int first[MaxM];
char str[MaxN][MaxN];
void add(int u,int x,LL s)
//将在第x篇文章中出现的短hashh值为u,长hashh值为s的单词加入hashh表
{
++tot;
h[tot].s=s;
h[tot].cnt=1;
h[tot].no=x;
h[tot].next=first[u];
first[u]=tot;
}
void hashh(int x,int u,LL s)
{int i;
for(i=first[u];i!=0;i=h[i].next)
if (s==h[i].s)//在hashh表出现过
{
if (h[i].no==x) return;
//也是在第x篇文章中出现，就不用管了
h[i].no=x;
h[i].cnt++;//出现的次数加1
return;
}
add(u,x,s);
}
void init()
{
int i;
scanf("%d%d%d",&N,&M,&L);
for(i=1;i<=N;i++)
scanf("%s",&str[i]);
ans=0;
}
void work()
{int i,j,u,k,k1;
LL s,k2;
k1=k2=1;
for(j=0;j<L-1;j++)
{
k1=k1*26%MinMod;//数量级
k2=k2*26%MaxMod;
}
for(i=1;i<=N;i++)
{
u=s=0;
for (j=0;j<L;j++)
{
u=(u*26+str[i][j])%MinMod;//短hashh值
s=(s*26+str[i][j])%MaxMod;//长hashh值
}
hashh(i,u,s);
k=strlen(str[i]);
for(j=L;j<k;j++)
{
u=((u-str[i][j-L]*k1)%MinMod+MinMod)%MinMod;//前面去一位后面加一位
s=((s-str[i][j-L]*k2)%MaxMod+MaxMod)%MaxMod;
u=(u*26+str[i][j])%MinMod;
s=(s*26+str[i][j])%MaxMod;
hashh(i,u,s);
}
}
}
void output()
{
int i;
for(i=1;i<=tot;i++)
if(h[i].cnt>=M) ++ans;
printf("%d
",ans);
}
int main(void)
{
init();
work();
output();
return 0;
}
单Hash的做法，事实上有很大可能出错的，某两个不同的字符串hash出来的值是一样的。
#include<bits/stdc++.h>
#define ll long long
#define base 31
using namespace std;
const int mod=1e9+7,maxm=2e6+10;
int n,m,l,ans;
int f[maxm],g[maxm];
ll p[1010]={1},hash1[maxm];
char s[1010];
inline int add(int x)
{
int tmp=x%maxm;
while(hash1[tmp]&&hash1[tmp]!=x)tmp=(tmp+1)%maxm;
return tmp;
}
int main()
{
scanf("%d%d%d",&n,&m,&l);
for(int i=1;i<l;i++)
p[i]=p[i-1]*base%mod;
while(n--)
{
scanf("%s",s+1);
int len=strlen(s+1);
ll sum=0;
for(int i=1;i<l;i++)
sum=(sum+p[l-1-i]*s[i])%mod;
for(int i=l;i<=len;i++)
{
sum=(sum+mod-p[l-1]*s[i-l]%mod)%mod;
sum=(sum*base+s[i])%mod;
int k=add(sum);
hash1[k]=sum;
if(g[k]!=n)
{
if(++f[k]==m)ans++;
g[k]=n;
}
}
}
printf("%d",ans);
return 0;
}