KMP算法

public static int getIndexOf(String s, String m){
    if(s == null || m == null || s.length() == 0 || s.length() == 0)
        return -1;
    char[] str1 = s.toCharArray();
    char[] str2 = s.toCharArray();
    int i1 = 0;
    int i2 = 0;
    int[] next = getNextArray(str2);

    while(i1 < str1.length && i2 < str2.length){
        // 相等的时候，都向前移动
        if(str1[i1] == str2[i2]){
            i1++;
            i2++;
        }else if(next[i2] == -1){ // i2到达0位置，无法向前跳，str1换个开头
            i1++;
        }else{ //i2还可以向前跳
            i2 = next[i2];
        }
    }
    return i2 == str2.length ? i1-i2 : -1;
}

// 算出next数组
public static int[] getNextArray(char[] ms){
    if(ms.length == 1)
        return new int[]{-1};
    int[] next = new int[ms.length];
    next[0] = -1;
    next[1] = 0;
    int i=2; // next数组的位置
    int cn = 0;
    while(i < next.length){
        if(ms[i-1] == ms[cn]){
            next[i++] = ++cn;
        }else if(cn > 0){ // 当前跳到cn位置的字符，和i-1位置的字符配不上
            cn = next[cn];
        }else{
            next[i++] = 0;
        }
    }
    return next;
}