title: Rabin Karp Algorithm Negative Hash
body: <p>I have this Rabin Karp implementation. Now the only thing I'm doing for rolling hash is subtract <code>power*source[i]</code> from the <code>sourceHash</code>. <code>power</code> is <code>31^target.size()-1 % mod</code>
  But I can't understand why we're adding <code>mod</code> to <code>sourceHash</code> when it becomes negative. I have tried adding other values but it doesn't work and it only works when we add <code>mod</code>. Why is this? Is there a specific reason why we're adding <code>mod</code> and not anything else (like a random big number for example).</p>
  <pre class="lang-js prettyprint-override"><code>int rbk(string source, string target){
          int m = target.size();
          int n = source.size();
          int mod = 128;
          int prime = 11;
          int power = 1;
          int targetHash = 0, sourceHash = 0;
          for(int i = 0; i &lt; m - 1; i++){
              power =(power*prime) % mod;
          }
          for(int i = 0; i &lt; target.size(); i++){
              sourceHash = (sourceHash*prime + source[i]) % mod;
              targetHash = (targetHash*prime + target[i]) % mod;
          }
          
          for(int i = 0; i &lt; n-m+1; i++){
              if(targetHash == sourceHash){
                  bool flag = true;
                  for(int j = 0; j &lt; m; j++){
                      if(source[i+j] != target[j]){
                          flag = false;
                          break;
                      }
                  }
                  if(flag){
                      return 1;
                  }
              }
              
              if(i &lt; n-m){
                  sourceHash = (prime*(sourceHash - source[i]*power) + source[i+m]) % mod;
                  if(sourceHash &lt; 0){
                      sourceHash += mod;
                  }
              }
          }
          return -1;
  }
  </code></pre>