题目描述 小可可是学校图书馆的管理员，现在他接手了一个十分棘手的任务。 由于学校需要一些材料，校长需要在文章中检索一些信息。校长一共给了小可可N篇文章，每篇文章为一个字符串。现在，校长需要他找到这样的单词，它至少在这N篇文章中的M篇文章里出现过，且单词长度为L。可是，工作量十分庞大，但校长又急需小可可完成这项任务。 现在他向你求助，需要你编写程序完成这项艰巨的任务。
输入 第1行3个正整数N，M，L，表示文章的数目，单词至少出现在M篇文章中和每个单词的长度。 接下来N行，每行一个字符串，表示一篇文章。 输出 仅一行，表示满足检索条件的单词数。
样例输入 3 2 2 noip istudycpp imacppstudent 样例输出 5
提示 这5个单词分别为：st，tu，ud，pp，cp。 对于20%的数据有1≤N,M≤10； 对于60%的数据有1≤N,M≤100； 对于100%的数据有1≤N,M≤2000，L≤1000。每篇文章长度不大于1000，均有小写字母组成。
人生第一道hash。 以前一直知道hash，是把信息转化成一个整数再放到数组里。但一直没有写过。直到上次考了这道。。。 我们可以把字符串看成一个26进制的数，对每一段字符串，我们记录两个信息。 u表示字符串的小hash值 v表示字符串的大hash值 如果u一样，就把它们链起来，但如果v又一样的话，就有错误了。但v值mod的大质数因为非常大，所以这个出错的概率是很小的。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define ll long long using namespace std; int n,m,ap,k1,u,ans,len,tot; ll v,k2; char s[1005]; const int minmod=999973; //小质数 const ll maxmod=(ll)(499999999999993); //大质数 struct ty { int p,cnt; ll maxhash; }Hash[1000005]; int head[1000005],Next[1000005]; void add(int x,int y,ll z) //添加进链表 { tot++; Hash[tot].maxhash=z; Hash[tot].cnt=1; Hash[tot].p=y; Next[tot]=head[x]; head[x]=tot; } void Find(int art,int u,ll v) { for(int i=head[u];i!=-1;i=Next[i]) //遍历小hash值的一条链 if(v==Hash[i].maxhash) //大hash值一样，就说明字符串一样 { if(art==Hash[i].p) return; //该文章已经出现过，就不用再加了 Hash[i].p=art; //更新是哪个文章，前面的文章不可能再出现，所以直接更新 Hash[i].cnt++; return; } add(u,art,v); } int main() { cin>>n>>ap>>m; for(int i=0;i<minmod;i++) head[i]=-1; k1=1;k2=1; for(int i=1;i<m;i++) { k1=k1*26%minmod; k2=k2*26%maxmod; } for(int i=1;i<=n;i++) { scanf("%s",s+1); len=strlen(s+1); u=0;v=0; for(int j=1;j<=m;j++) { u=(u*26+s[j])%minmod; v=(v*26+s[j])%maxmod; } Find(i,u,v); for(int j=m+1;j<=len;j++) { u=((u-k1*s[j-m])%minmod+minmod)%minmod;//去掉第一位 v=((v-k2*s[j-m])%maxmod+maxmod)%maxmod; u=(u*26+s[j])%minmod;//添加最后一位 v=(v*26+s[j])%maxmod; Find(i,u,v); } } for(int i=1;i<=tot;i++) if(Hash[i].cnt>=ap) ans++; cout<<ans; return 0; }