Description

小可可是學校圖書館的管理員，現在他接手了一個十分棘手的任務。
由于學校需要一些材料，校長需要在文章中檢索一些信息。校長一共給了小可可N篇文章，每篇文章為一個字符串?，F在，校長需要他找到這樣的單詞，它至少在這N篇文章中的M篇文章里出現過，且單詞長度為L?？墒?#xff0c;工作量十分龐大，但校長又急需小可可完成這項任務。
現在他向你求助，需要你編寫程序完成這項艱巨的任務。

Input

第1行3個正整數N，M，L，表示文章的數目，單詞至少出現在M篇文章中和每個單詞的長度。
接下來N行，每行一個字符串，表示一篇文章。

Output

僅一行，表示滿足檢索條件的單詞數。

Sample Input

3 2 2
noip
istudycpp
imacppstudent

Sample Output

5
【樣例解釋】
這5個單詞分別為：st，tu，ud，pp，cp。

Data Constraint

對于20%的數據有 1≤N,M≤10；
對于60%的數據有 1≤N,M≤100；
對于100%的數據有 1≤N,M≤2000，L≤1000。每篇文章長度不大于1000，均有小
寫字母組成。

Solution

• 這題是典型的 字符串Hash ，開散列。

• 先枚舉每篇文章，在枚舉其中的每個單詞，把單詞轉換成模意義下26進制，質數取 109+7 。

• 之后把這個數放進 Hash 表中，判斷是否存在，達到m次即答案+1，上限取 2?106 。

枚舉過程中注意邊加邊判斷，總時間復雜度為 O(N?(N?L)) ！

Code

#include<cstdio> #include<cstring> using namespace std; const int N=1002,M=N*N*2,mo=1e9+7; int n,m,l,ans; int f[M],g[M]; long long p[N],h[M]; char s[N]; inline int hash(int x) {int y=x%M;while(h[y] && h[y]!=x) y=(y+1)%M;return y; } int main() {scanf("%d%d%d",&n,&m,&l);for(int i=p[0]=1;i<l;i++) p[i]=p[i-1]*26%mo;n++;while(--n){scanf("%s",s+1);int len=strlen(s+1);long long sum=0;for(int i=1;i<l;i++) sum=(sum+p[l-1-i]*s[i])%mo;for(int i=l;i<=len;i++){sum=(sum+mo-p[l-1]*s[i-l]%mo)%mo;sum=(sum*26+s[i])%mo;int k=hash(sum);h[k]=sum;if(g[k]!=n){if(++f[k]==m) ans++;g[k]=n;}}}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3870. 【NOIP2014八校联考第4场第1试10.19】单词检索(search)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。