title: Count amount of String occurrences and comparisons (KMP)
body: <p>I'm trying to count the amount of pattern occurrences and needed comparisons (called matches in the code below), using search algorithm <strong>KMP</strong>. </p>
  
  <p>I've tried doing the following:</p>
  
  <pre><code>public class KMP {
  
      private String pat;
      private int[][] dfa;
      private static int match;
      private static int count;
  
      public KMP(String pat) {
          // Build DFA from pattern.      
          this.pat = pat;
          int M = pat.length();
          int R = 256;
          dfa = new int[R][M];
          dfa[pat.charAt(0)][0] = 1;
          for (int X = 0, j = 1; j &lt; M; j++) {
              // Compute dfa[][j].         
              for (int c = 0; c &lt; R; c++) {
                  dfa[c][j] = dfa[c][X];           // Copy mismatch cases.        
                  dfa[pat.charAt(j)][j] = j + 1;   // Set match case.    
                  X = dfa[pat.charAt(j)][X];       // Update restart state.   
              }
          }
      }
  
      public int search(String txt) {
          // Simulate operation of DFA on txt.    
          int i, j, N = txt.length(), M = pat.length();
          for (i = 0, j = 0; i &lt; N &amp;&amp; j &lt; M; i++) {
              j = dfa[txt.charAt(i)][j];
          }
          if (j == M) {
              return i - M; // found (hit end of pattern)  
          } else {
              return N;     // not found (hit end of text)  
          }
      }
  
      public static void main(String[] args) {
  
          String pat = "babba";
          String txt = "aaaaaaaaaaaabbaaababbaaaaababbaaaa";
          int lastIndex = 0;
  
          KMP kmp = new KMP(pat);
          int offset = kmp.search(txt);
  
          System.out.println("text:    " + txt);
          System.out.print("pattern: ");
  
          while (lastIndex != txt.length()) {
              for (int i = 0; i &lt; offset; i++) {
                  lastIndex++;
                  match++;
              }
              count++;
          }
  
          System.out.println(pat);
          System.out.println("count:   " + count);
          System.out.println("match:   " + match);
      }
  }
  </code></pre>
  
  <p>My code works just fine when compiling it like this, but when I change the <code>String txt</code> attribute to something like <code>aaaaaaaaaaaabbaaababbaaaaababbaaaababba</code>, It gives me an unexpected, negative count value (also, it takes about 30 seconds to actually run the code).</p>
  
  <p>I'm trying to find a better solution of counting the occurrences and I'd also like to know what's wrong with my code, since it only works in some cases.</p>