小可可是学校图书馆的管理员，现在他接手了一个十分棘手的任务。由于学校需要一些材料，校长需要在文章中检
索一些信息。校长一共给了小可可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。
#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\n",ans);
}
int main(void)
{
init();
work();
output();
return 0;
}
#include<bits/stdc++.h>#define ll long long#define mod 28282789#define L 1001using namespace std;inline void read(int &x){ int datta=0;char chchc=getchar();bool okoko=0; while(chchc<‘0‘||chchc>‘9‘){if(chchc==‘-‘)okoko=1;chchc=getchar();} while(chchc>=‘0‘&&chchc<=‘9‘){datta=datta*10+chchc-‘0‘;chchc=getchar();} x=okoko?-datta:datta;}int n,m,l,len,times[mod+10],ans;int clear[L],nc;ll base=26,q[L],hx[L];char c[L];bool did[mod+10];ll fk(int a,int b){return (hx[b]-(hx[a-1]*q[b-a+1])%mod+mod)%mod;} int main(){ read(n),read(m),read(l);q[0]=1; for(int i=1;i<=L;i++)q[i]=(q[i-1]*base)%mod; for(int i=1;i<=n;i++){ scanf("%s",c+1); len=strlen(c+1); for(int i=1;i<=len;i++)hx[i]=(hx[i-1]*base+c[i]-‘a‘+1)%mod; for(int i=1;i+l-1<=len;i++){ ll tp=fk(i,i+l-1); if(!did[tp]){ did[tp]=true;clear[++nc]=tp; if(++times[tp]==m)ans++; } } for(int i=1;i<=nc;i++){did[clear[i]]=false;} nc=0; } printf("%d\n",ans); return 0;}
原文：https://www.cnblogs.com/cutemush/p/12297616.html