title: Prime Number and Block Length in Karp Rabin
body: <p>I found a rabin karp code from <a href="http://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/" rel="nofollow">that</a> site and changed to try. Changed code is below. You can see words and their hash values in hashtable.txt. for below example hashtable.txt seems right. </p>
  
  <p>But when I changed M (block length) to 150 I am getting wrong results. For example in hashtable.txt first line and 6th line must be same but their hash values are different.</p>
  
  <p>Or when I changed q (prime number) to 683303 it's getting wrong results too.</p>
  
  <p>What's the relation between prime number and block length in rabin karp algorithm, and what's reason of wrong results?</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;string.h&gt;
  #include &lt;fstream&gt;
  #include &lt;iostream&gt;
  // d is the number of characters in input alphabet
  #define d 256 
  int M = 80;
  /*  
  txt  -&gt; text
  q    -&gt; A prime number
  */
  using namespace std;
  
  void writeTable(char *txt, int q)
  {
  ofstream myfile;
  myfile.open ("hashtable.txt");
  int N = strlen(txt);
  int i, j;
  int t = 0; // hash value for txt
  int h = 1;
  
  // The value of h would be "pow(d, M-1)%q"
  for (i = 0; i &lt; M-1; i++)
      h = (h*d)%q;
  
  // Calculate the hash value of pattern and first window of text
  for (i = 0; i &lt; M; i++)
  {
      t = (d*t + txt[i])%q;
  }
  
  // Slide the pattern over text one by one 
  for (i = 0; i &lt;= N - M; i++)
  {
      myfile &lt;&lt; t &lt;&lt;" ";
      for (long z = i; z &lt; M+i; z++){myfile&lt;&lt;txt[z];}myfile&lt;&lt;"\n";
  
      // Calulate hash value for next window of text: Remove leading digit, 
      // add trailing digit           
      if ( i &lt; N-M )
      {
          t = (d*(t - txt[i]*h) + txt[i+M])%q;
  
          // We might get negative value of t, converting it to positive
          if(t &lt; 0) 
            t = (t + q); 
      }
  }
  
  myfile.close();
  }
  
  /* Driver program to test above function */
  int main()
  {
      char *txt ="abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde";
  
  int q = 683303;  // A prime number
  
  writeTable(txt, q);
  
  printf("finish");
  getchar();
  return 0;
  }
  </code></pre>