数据结构：KMP算法

public class 暴力法 {
    public static void main(String[] args) {
        String s1 = "北京欢迎你";
        String s2 = "欢迎";
        System.out.println(index(s1, s2));
    }

    public static int index(String s1, String s2) {
        int i = 0;
        int j = 0;
        boolean flag = false;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
            if (j == s2.length()) {
                flag = true;
                break;
            }
        }
        if (flag) {
            return i - j;
        } else {
            return -1;
        }
    }
}

public class KMP算法 {
    public static void main(String[] args) {
        String s1 = "BBCABCDABABCDABCDABDE";
        String s2 = "ABCDABD";
//        int[] next = kmpNext(s2);
//        for (int x : next) {
//            System.out.print(x);
//        }
        System.out.println(search(s1, s2));
    }

    public static int[] kmpNext(String s) {
        int[] next = new int[s.length()];
        int i = 0;
        for (i = 0; i < s.length(); i++) {
            //拿到索引为i的子串temp
            String temp = s.substring(0, i + 1);
            //找公共的前后缀长度
            next[i] = together(temp);
        }
        return next;
    }

    public static int together(String s) {
        int flag = 0;
        for (int x = 0; x < s.length() - 1; x++) {
            String front = s.substring(0, x + 1);
            String tail = s.substring(s.length() - x - 1, s.length());
            if (front.equals(tail)) {
                flag = x + 1;
            }
        }
        return flag;
    }

    public static int search(String s1, String s2) {
        int[] next = kmpNext(s2);
        int i = 0;
        int j = 0;
        int n = 0;
        boolean flag = false;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
                n++;
            } else {
                if (n == 0) {
                    j++;
                } else {
                    //移动位数=已经匹配的字符数-对应的部分匹配值
                    int x = n - next[j - 1];
                    //将i向后移动x位
                    for (int m = 0; m < x; m++) {
                        i++;
                    }
                    //将j值为零
                    j = 0;
                    //将已经匹配到的字符数重置为0
                    n = 0;
                }
            }
            if (j == s2.length()) {
                flag = true;
                break;
            }
        }
        if (flag) {
            return i - j;
        } else {
            return -1;
        }
    }
}