public class KMP {
   int[]fail;
   char[]text;
   char[]pattern;
   
   public void init() {
      initPattern("ABACABAD");
      initText("ABAABABCDFABACABADC");
   }
   public void start() {
      int matches;
      preProsessPattern();
      matches = match();
      System.out.println("Pattern was found "+matches+" times."); 
   }

   void initPattern(String p) {
      pattern = new char[p.length()];
      for (int i = 0; i < p.length(); i++) {
	 pattern[i] = p.charAt(i);
      }
   }

   void initText(String t) {
      text = new char[t.length()];
      for (int i = 0; i < t.length(); i++) {
	 text[i] = t.charAt(i);
      }
   }

   void preProsessPattern() {
      int j = 1, k = 0;
      fail = new int[pattern.length + 1];
      for (int i = 1 ; i < fail.length ; i++)
          fail[i] = 0;
      fail[0] = -1;
      while (j < pattern.length - 1) {
	 while (k > 0 && (pattern[j]) != (pattern[k]))
	   k = fail[k];
	 j++;
	 k++;
	 if (pattern[j] == pattern[k])
	   fail[j] = fail[k];
	 else
	   fail[j] = k;
      }
   }

   int match() {
      int numberOfMatches = 0;
      int j = 0, i = 0;
      do {
	 if (j < 0 || pattern[j] == text[i]) {
	    j++;
	    i++;
	 } else
	   j = fail[j];
	 if (j >= pattern.length) {
	    System.out.println("Pattern found from "+(i-pattern.length));
	    numberOfMatches++; 
	    j = fail[j];
	 }
      } while (i < text.length);
      return numberOfMatches;
   }

}