1、暴力匹配

最简单的方式就是直接进行两个循环的暴力匹配，这个方法很容易就想到，但是时间复杂度较高。原理也比较简单，模式串和文本串逐个字符进行比较，如果遇见不相同的字符时结束当前次的比较，文本串指针下移重新和模式串进行比较。

public int violence(String pattern, String text) {
    char[] patterns = pattern.toCharArray(), texts = text.toCharArray();
    for (int i = 0; i <= texts.length - patterns.length; i++) {
        int j = 0;
        while (j < patterns.length) {
            if (texts[i + j] != patterns[j]) break;
            j++;
        }
        if (j == patterns.length) return i;
    }
    return -1;
}

2、KMP算法

由于暴力会重复计算很多不必要判断的字符，因此就提出一种最长前后缀的优化方式来减少重复匹配的次数，因为是基于暴力匹配的，在不满足优化的条件的最坏情况下，依然会退化成为暴力匹配的方式。

这里需要注意的就是 next 数组，其中包含了如果当前额字符不匹配，模式串将要移动的位置信息。如果以当前字符为结尾的字符串的最长公共前后缀的长度存在，也就是说当此字符不匹配时模式串的指针将会自动移动这么长的位置然后进行比较。

public int KMP(String pattern, String text) {
    char[] patterns = pattern.toCharArray(), texts = text.toCharArray();
    int[] next = new int[patterns.length];
    next[0] = -1;
    //  求取模式串的 next 数组, 方便后续的计算
    for (int i = 1, j = -1; i < next.length; i++) {
        while (j != -1 && patterns[i] != patterns[j + 1]) j = next[j];
        if (patterns[i] == patterns[j + 1]) j++;
        next[i] = j;
    }
    //  按照暴力匹配的方式进行匹配
    for (int i = 0, j = -1; i < texts.length; i++) {
        while (j != -1 && patterns[j + 1] != texts[i]) j = next[j];
        if (patterns[j + 1] == texts[i]) j++;
        if (j == patterns.length - 1) return i - j;
    }
    return -1;
}

3、Sunday算法

和 KMP 的优化方式差不多，都是寻找相同的节点来降低重复匹配的次数，从而优化匹配的速度，在不满足优化条件的情况下依然会导致退化成为暴力匹配。算法思想是当前字符不匹配时，模式串的指针向前移动，找到第一个与文本串当前字符相同的字符，使得这两个字符对齐，再进从头进行比较。

引入了一个 Last_position 的这样一个数组来存储最近的字符位置，这样就可以在一次预处理之后能够快速的获得左边的第一个指定字符的位置。

public int sunday(String pattern, String text) {
    char[] patterns = pattern.toCharArray(), texts = text.toCharArray();
    int[] lastPosition = new int[26];
    for (int i = 0; i < 26; i++) {
        lastPosition[i] = -1;
    }
    for (int i = 0; i < patterns.length; i++) {
        lastPosition[patterns[i] - 'a'] = i;
    }
    for (int i = 0; i <= texts.length - patterns.length;
        i += (patterns.length - lastPosition[texts[i + patterns.length] - 'a'])) {
        int j = 0;
        for (j = 0; j < patterns.length; j++) {
            if (patterns[j] == texts[i + j]) continue;
            break;
        }
        if (j == patterns.length) return i;
    }
    return -1;
}

4、Shift-And算法

和前两种的优化方式不同，该种方法引入了一个新的数据结构来定义匹配的行为，数字 P 二进制位的 1 所处位置表示当前的模式串的前 n 个已经完成匹配，数组 code 代表模式串每个字符所处的位置信息。

首先假设当前位的字符是可以完成配对的 p = p << 1 | 1 ，现在的 p 的二进制表示肯定是 1111... 这样的格式。既然进行了假设，那么接下来就需要证明假设成立，这时候 code 数组就可以使用了，我们快速确定当前字符在模式串的第几个位置，也就是取出来的数据的二进制位为 1 ，式子 p & code[s[i]] 如果所属位依旧是 1 既验证成功。

public int shift_and(String pattern, String text) {
    char[] patterns = pattern.toCharArray(), texts = text.toCharArray();
    int[] position = new int[26];
    for (int i = 0; i < patterns.length; i++) {
        position[patterns[i] - 'a'] |= (1 << i);
    }
    int p = 0;
    for (int i = 0; i < texts.length; i++) {
        p = (p << 1 | 1) & position[texts[i] - 'a'];
        if ((p & (1 << patterns.length - 1)) > 0) return i - patterns.length + 1;
    }
    return -1;
}