title: Rolling hash: my codes fails with modulo for long string
body: <p>I'm trying to solve <a href="https://leetcode.com/problems/longest-repeating-substring/" rel="nofollow noreferrer">https://leetcode.com/problems/longest-repeating-substring/</a>
  I want to use rolling hash to match strings.
  However, my codes don't seem to work when I deal with modulo.
  For a string with all same characters, the maximum length of repeating substring should be string.length - 1.</p>
  
  <pre><code>public class Main {
      public static void main(String[] args) {
          String str = "bbbbbbbbbbbbbbbbbbb";
          System.out.println(str.length() - 1);
          Solution s = new Solution();
          System.out.println(s.longestRepeatingSubstring(str));
      }
  }
  class Solution {
          public int  longestRepeatingSubstring(String S) {
              HashSet&lt;Long&gt; h = new HashSet();
              long mod = (long)1e7 + 7;
              for(int i = S.length() - 1; i &gt;0; i--){
                  h = new HashSet();
                  long c = 0;
                  int j = 0;
                  for(; j &lt; i; j ++){
                      c = (c*26 % mod  + S.charAt(j) - 'a')% mod;
                  }
  
                  h.add(c);
                  for(; j &lt; S.length(); j++){
                      c -= (S.charAt(j - i ) - 'a') * Math.pow(26,i-1)% mod;
  
                      c = (c*26 % mod + S.charAt(j) - 'a')% mod;
  
                      if(h.contains(c)){
                          return i;
                      }
                      h.add(c);
  
                  }
              }
              return 0;
          }
      }
  </code></pre>
  
  <p>Playground for my codes: <a href="https://leetcode.com/playground/F4HkxbFQ" rel="nofollow noreferrer">https://leetcode.com/playground/F4HkxbFQ</a></p>