Guest User

Untitled

a guest
Aug 8th, 2012
16
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.71 KB | None | 0 0
  1. Trouble with rolling hash implementation
  2. int MUL = 37;
  3. int MOD = 9999991;
  4.  
  5. for(int i = 1 , pwr = 1 ; i < plen ; i++) pwr = (pwr * MUL) % MOD;
  6. long long hash = number[0];
  7. long long revHash = number[plen - 1];
  8. for(int i = 1 ; i < plen ; i++)
  9. {
  10. hash = (MUL*hash + number[i])%MOD;
  11. revHash = (revHash*MUL + number[plen - i - 1])%MOD;
  12.  
  13. }
  14.  
  15. cout << hash << " " << revHash <<"n";
  16.  
  17. int cnt = (hash == revHash);
  18.  
  19. for(int i = plen ; i < numbers ; i++)
  20. {
  21. hash = (hash + (MOD - pwr)*number[i - plen])%MOD;
  22. hash = (hash*MUL + number[i])%MOD;
  23.  
  24.  
  25. revHash = ((revHash + MOD - number[i - plen]))%MOD;
  26. revHash = (revHash + pwr*number[i])%MOD;
  27.  
  28. cnt += (hash == revHash);
  29.  
  30. cout << hash << " " << revHash << "n";
  31.  
  32. }
Advertisement
Add Comment
Please, Sign In to add comment