Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Aug 8th, 2012  |  syntax: None  |  size: 0.71 KB  |  hits: 6  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }