串--模式匹配算法

BF算法--朴素匹配算法（暴力匹配算法）

主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。O(n*m)

public int bf(char[] masterChar, char[] matchChar) {
        //目标数据从第一个开始比对
        char first = matchChar[0];
        //剩余最大长度，从0开始比较到max时，没有匹配到数据，就不用匹配了，后边数据长度不够
        int max = masterChar.length - matchChar.length;

        //for循环的含义为，继续寻找下一个匹配第一个字符的下标
        for (int i = 0; i <= max; i++) {
            //
            if (masterChar[i] != first) {
                while (++i <= max && masterChar[i] != first) {

                }
            }

            //碰到数据与first相等，此时下标为i
            if (i <= max) {
                //继续匹配i下一个元素与target元素匹配
                int j = i + 1;
                int end = j + matchChar.length - 1;
                for (int k = 1; j < end && masterChar[j]
                    == matchChar[k]; j++, k++) {

                }

                //如果顺利匹配到最后一位且成功，则匹配成功
                if (j == end) {
                    return i;
                }
            }
        }
        return -1;
    }

KMP模式匹配算法：

在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。
好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

public static int kmp(char[] masterChar, char[] matchChar) {

        //获取到最长前缀子串数组
        int[] next = getNext(matchChar);
        int j = 0;
        for (int i = 0; i < masterChar.length; ++i) {
            // 一直找到a[i]和b[j]
            while (j > 0 && masterChar[i] != matchChar[j]) {
                //比较的是第j个数据，如果数据不等，则需要找到。前面数据的最长可匹配子串的下一个字符，是否相等。
                j = next[j - 1] + 1;
            }
            if (masterChar[i] == matchChar[j]) {
                ++j;
            }
            // 找到匹配模式串的了
            if (j == matchChar.length) {
                return i - matchChar.length + 1;
            }
        }
        return -1;
    }
    private static int[] getNext(char[] matchChar) {
        int[] next = new int[matchChar.length];
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < matchChar.length; ++i) {
            //如果上一个匹配的字符的下一个字符，没有等于要匹配的下一个字符。
            // 则在上一个字符能找到的最长前缀子串中，找到最长前缀子串。判断最长前缀子串的下一个字符是不是与其匹配
            while (k != -1 && matchChar[k + 1] != matchChar[i]) {
                k = next[k];
            }
            if (matchChar[k + 1] == matchChar[i]) {
                ++k;
            }
            next[i] = k;
        }
        return next;
    }