KMPËã·¨

 public static int[] getNext(char[] chars){
        if (chars.length == 1){
            return new int[]{ -1 };
        }
        int [] next = new int[chars.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < chars.length){
            if ( chars[pos-1] == chars[cn]){
                next[pos++] = ++cn;
            }else if (cn > 0){
                cn = next[cn];
            }else {
                next[pos++] = 0;
            }
        }
        return next;
   }

    public static int getIndex(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() == 0 ||
             str2.length() > str1.length()) return -1;
        int i1 = 0;
        int i2 = 0;
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int [] next = getNext(chars2);
        while (i1 < str1.length() && i2 < str2.length()){
            if (chars1[i1] == chars2[i2]){
                i1++;
                i2++;
            }else if (next[i2] == -1){
                i1++;
            }else {
                i2 = next[i2];
            }
        }
        return i2 == str2.length() ? i1 - i2 : -1;
    }