fork download 
  1. /// vn.spoj.com/problems/SUBSTR/
  2.  
  3. /// hash str by muoii
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 0
  9. #define maxc 0
  10. #define len 31
  11. #define oo 1000000007
  12. #define mid ((l+r)>>1)
  13. #define meset(a,x) memset(a,x,sizeof(a))
  14. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  15. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  16. /// HASH:
  17.  
  18. struct strig{
  19.     int n;
  20.     string s;
  21.     long long base,modul;
  22.     long long hashall;
  23.     vector<int> HASH;
  24.     vector<int> pow;
  25.  
  26.     strig(const string &str,const long long &bse,const long long &modulo): n(str.size()), s("$"+str), base(bse), modul(modulo), hashall(-1), HASH(0), pow(0) {};
  27.     void calcall(){
  28.         hashall=0;
  29.  
  30.         for(int i=1;i<=n;i++)
  31.             hashall=(hashall*base + s[i]-'a'+1)%modul;
  32.     }
  33.  
  34.     void calcvec(){
  35.         HASH.resize(n+1);
  36.         pow.resize(n+1);
  37.         HASH[0]=0;pow[0]=1;
  38.  
  39.         for(int i=1;i<=n;i++)
  40.         {
  41.             pow[i]=(pow[i-1]*base)%modul;
  42.             HASH[i]=(HASH[i-1]*base + s[i]-'a'+1)%modul;
  43.         }
  44.     }
  45.  
  46.     long long gethash(const int &l,const int &r)
  47.     {
  48.         return (HASH[r] - HASH[l-1]*pow[r-l+1] + modul*modul)%modul;
  49.     }
  50. };
  51. int main()
  52. {
  53.     #ifdef dmdd
  54.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  55.     #endif // dmdd
  56.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  57.  
  58.     long long base =31,modulo=1000000003LL;
  59.  
  60.     int m,n;
  61.     string str;
  62.  
  63.     cin>>str;
  64.     strig a(str,base,modulo);
  65.  
  66.     cin>>str;
  67.     strig b(str,base,modulo);
  68.  
  69.     a.calcvec();
  70.     b.calcall();
  71.  
  72.     for(int i=1;i+b.n-1<=a.n;i++)
  73.         if(a.gethash(i,i+b.n-1)==b.hashall)
  74.             cout<<i<<" ";
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
aaababa
aba
stdout 
3 5
https://ideone.com/DBVBZd
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!