Advertisement
Mysakure

string hash

Oct 23rd, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. /**
  2.  *    author:  MySakure
  3.  *    created: 23.10.2019 19:48:14      
  4. **/
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. #define ull unsigned long long
  8. const int maxn=1e6+10;
  9. int n;
  10. string s;
  11. ull hashs[maxn],hash1[maxn],bin[maxn];
  12. ull p=233;
  13. int ans=0;
  14. multiset<ull>st;
  15. signed main() {
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(NULL);
  18. #ifdef mysakure
  19.     freopen("in1.txt","r",stdin);
  20. #endif
  21.  
  22.     cin>>s;
  23.     int len=s.size();
  24.     for(int i=1;i<=len;++i)hash1[i]=hash1[i-1]*p+s[i-1]-'a';
  25.     st.insert(hash1[len]);
  26.     bin[0]=1;
  27.     for(int i=1;i<=maxn;++i)bin[i]=bin[i-1]*p;
  28.     for(int i=1;i<=len;++i){
  29.         st.insert((hash1[len]-hash1[i]*bin[len-i])*bin[i]+hash1[i]);
  30.     }
  31.     cin>>n;
  32.     while(n--){
  33.         cin>>s;
  34.         ans=0;
  35.         int l=s.size();
  36.         for(int i=1;i<=l;++i){
  37.             hashs[i]=hashs[i-1]*p+s[i-1]-'a';
  38.         }
  39.         for(int i=1;i+len-1<=l;++i){
  40.             if(st.count(hashs[i+len-1]-hashs[i-1]*bin[len])){
  41.                 ++ans;
  42.             }
  43.         }
  44.         cout<<ans<<'\n';
  45.     }
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement