/**
 * An implementation of the Knuth-Morris-Pratt algorithm
 * @author William Fiset, william.alexandre.fiset@gmail.com
 **/

public class KMP {

  // Given a pattern and a text kmp finds all the places that the pattern 
  // is found in the text (even overlapping pattern matches)
  static java.util.List <Integer> kmp(String txt, String pat) {

    java.util.List <Integer> matches = new java.util.ArrayList<>();
    if (txt == null || pat == null) return matches;
    
    int m = pat.length(), n = txt.length(), i = 0, j = 0;
    if (m > n) return matches;

    int[] arr = kmpHelper(pat, m);

    while (i < n) {
      if (pat.charAt(j) == txt.charAt(i)) { j++; i++; }
      if (j == m) {
        matches.add(i-j);
        j = arr[j-1];
      } else if (i < n && pat.charAt(j) != txt.charAt(i)) {
        if (j != 0) j = arr[j-1];
        else i = i+1;
      }
    }

    return matches;

  }

  // For each index i compute the longest match between the proper
  // prefix starting at 0 and the proper suffix starting at i
  static int[] kmpHelper(String pat, int m) {
    int [] arr = new int[m];
    for (int i = 1, len = 0; i < m;) {
      if (pat.charAt(i) == pat.charAt(len)) {
        arr[i++] = ++len;
      } else {
        if (len > 0) len = arr[len-1];
        else i++;
      }
    }
    return arr;
  }  

  public static void main(String[] args) {
    
    java.util.List <Integer> matches = kmp("abababa", "aba");
    System.out.println(matches); // [0, 2, 4]

    matches = kmp("abc", "abcdef");
    System.out.println(matches); // []

    matches = kmp("P@TTerNabcdefP@TTerNP@TTerNabcdefabcdefabcdefabcdefP@TTerN", "P@TTerN");
    System.out.println(matches); // [0, 13, 20, 51]

  }

}