/**
 * 字符串模式匹配
 */
import java.util.Arrays;

public class StringMatch {
 /**
  * @param string1
  * @param string2
  * @return
  */
 public static int indexOf(String string1, String string2, int pos) {
  int i = pos, j = 0;
  while (i < string1.length()) {
   while (j < string2.length()) {
    if (string1.charAt(i + j) == string2.charAt(j)) {
     j++;
    } else {
     break;
    }
   }
   if (j == string2.length())
    return i;
   else {
    i++;
    j = 0;
   }
  }
  return -1;
 }
 
 public static int indexOfKMP(String string1, String string2, int pos) {
  
  int[] next = new int[string2.length()];
  
  generateNextval(string2, next);
  
  int i = pos, j = 0;
  while (i < string1.length() && j < string2.length()) {
   if (j == -1 || string1.charAt(i) == string2.charAt(j)) {
    //繼續(xù)比較后繼字符
    i++;
    j++;
   } else {
    //模式串向右移動
    j = next[j];  
   }
  }
  if (j == string2.length())
   //匹配成功
   return i - string2.length();
  else
   return -1;
 }
 
 private static void generateNext(String modelstring, int[] next) {
  int i = 0, j = -1;
  next[0] = -1;
  while (i < modelstring.length() - 1) {
   if (j == -1 || modelstring.charAt(i) == modelstring.charAt(j)) {
    i++;
    j++;
    next[i] = j;
   } else {
    j = next[j];
   }
  }
 }
 
 private static void generateNextval(String modelstring, int[] next) {
  int i = 0, j = -1;
  next[0] = -1;
  while (i < modelstring.length() - 1) {
   if (j == -1 || modelstring.charAt(i) == modelstring.charAt(j)) {
    i++;
    j++;
    if (modelstring.charAt(i) != modelstring.charAt(j))
     next[i] = j;
    else
     next[i] = next[j];
   } else {
    j = next[j];
   }
  }
 }
 
 private static void testGenerateNext() {
  String a = "abaabcac";
  int[] next = new int[a.length()];
  int[] nextval = new int[a.length()];
  generateNext(a, next);
  generateNextval(a, nextval);
  System.out.println(Arrays.toString(next));
  System.out.println(Arrays.toString(nextval));
 }
 
 public static void main(String[] args) {
  System.out.println(indexOfKMP("ababcabcacbab", "abcac", 0));
//  testGenerateNext();
  
 }
}