fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. ll mod = 1000000007;
  6. #define max 100005
  7. int p = 31;
  8.  
  9. ll hashfunction[max], power[max];
  10.  
  11. void precompute(string text, int n){
  12.  
  13.     power[0]=1;
  14.     hashfunction[0] = text[0]-'a'+1;
  15.     ll pow = p;
  16.     for(int i=1; i<n; i++){
  17.         power[i] = pow;
  18.         hashfunction[i] = (hashfunction[i-1] + ((text[i]-'a'+1)*pow)%mod)%mod;
  19.         pow = (pow * p)%mod;
  20.     }
  21. }
  22.  
  23. ll getHash(int l, int r){
  24.     if(l==0) return hashfunction[r];
  25.     else return (mod + hashfunction[r] - hashfunction[l-1])%mod;
  26. }
  27.  
  28. ll computeHashofstring(string pattern){
  29.     ll hash_value = 0;
  30.     for(int i=0; i<pattern.length(); i++){
  31.         hash_value = (hash_value + ((pattern[i]-'a'+1)*power[i])%mod)%mod;
  32.     }
  33.     return hash_value;
  34. }
  35.  
  36. vector<int> solve(string text, string pattern){
  37.  
  38.     vector<int> v;
  39.  
  40.     precompute(text, text.length());
  41.     ll hashofpattern = computeHashofstring(pattern);
  42.  
  43.     int left=0, right=pattern.length()-1;
  44.     while (right<text.length())
  45.     {   
  46.         if((hashofpattern*power[left])%mod == getHash(left,right)){
  47.             v.push_back(left);
  48.         }
  49.  
  50.         left++,right++;
  51.     }
  52.  
  53.     return v;
  54. }
  55.  
  56. int main(){
  57.  
  58.     string text, pattern;
  59.     cin >> text >> pattern;
  60.  
  61.     vector<int> v = solve(text, pattern);
  62.  
  63.     for(int i=0; i<v.size(); i++) cout << v[i] << '\n';
  64.  
  65.     return 0;
  66. }
Success #stdin #stdout 0s 4300KB
comments (?)
stdin
copy 
hdddhababababijie
abab
stdout
copy 
5
7
9
https://ideone.com/xPGdZ4
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!