package kmp;

public class TextBookKMPMatcher {

  private String pattern;
  private int[] prefixFunction;
  private String text;
  private int position;
  private int matches;

  private void createPrefixFunction() {
    prefixFunction = new int[pattern.length()];
    // Implementation note?
    prefixFunction[1] = 0;
    int matches1 = 0;
    for (int suffixEnd = 2; suffixEnd <= pattern.length(); suffixEnd++) {
      char nextChar = pattern.charAt(suffixEnd);
      while (matches1 > 0 && pattern.charAt(matches1 + 1) != nextChar) {
        matches1 = prefixFunction[matches1];
      }
      if (pattern.charAt(matches1 + 1) == pattern.charAt(suffixEnd)) {
        matches1++;
      }
      prefixFunction[suffixEnd] = matches1;
    }
  }

  public TextBookKMPMatcher(String pattern) {
    if (pattern == null) {
      throw new IllegalArgumentException("null pattern");
    }
    if (pattern.length() == 0) {
      throw new IllegalArgumentException("empty pattern");
    }
    this.pattern = pattern;
    text = "";
    createPrefixFunction();
  }

  public void setText(String text) {
    this.text = text;
    position = 0;
    matches = 0;
  }

  public int nextMatch() {
    while (position <= text.length()) {
      // Invariant:
      // matches is the size of the largest prefix of pattern that is identical
      // to a suffix of the characters in text up to but not including the one
      // at position.
      char nextChar = text.charAt(position);
      while (matches > 0 && pattern.charAt(matches + 1) != nextChar) {
        // Run time note?
        matches = prefixFunction[matches];
      }
      if (pattern.charAt(matches + 1) == nextChar) {
        matches++;
      }
      position++;
      if (matches == pattern.length()) {
        matches = prefixFunction[matches];
        // Implementation note?
        return position - pattern.length() - 1;
      }
    }
    return -1;
  }

}