字符串匹配这个功能，是非常常见的功能，比如"Hello"里是否包含"el"？

Java里用的是indexOf函数，其底层就是字符串匹配算法。主要分类如下：

BF算法

原理

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法

这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高

比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串

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

代码实现

package com.rubin.algorithm.charsetmatch;

/**
 * 暴力匹配算法，也叫朴素匹配算法
 * 我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)
 * m:为匹配串长度
 * n:为主串长度
 */
public class BruteForce {

    public static boolean isMatch(String origin, String match) {
        for (int i = 0; i <= (origin.length() - match.length()); i++) {
            if (origin.substring(i, i + match.length()).equals(match)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("ccaaac", "caaac"));
        System.out.println(isMatch("ccaaac", "abc"));
    }

}

RK算法

原理

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的

每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低

RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了

代码实现

package com.rubin.algorithm.charsetmatch;

/**
 *  Rabin-Karp 算法
 *
 *  RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式
 * 串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这
 * 里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模
 * 式串和子串比较的效率就提高了
 *
 * T = O(m+n)
 * m:为匹配串长度
 * n:为主串长度
 *
 * 适用于匹配串类型不多的情况，比如：字母、数字或字母加数字的组合 62 (大小写字母+数字)
 */
public class RabinKarp {

    public static boolean isMatch(String origin, String match) {
        int matchhash= str2hash(match);
        for (int i = 0; i <= (origin.length() - match.length()); i++) {
            if (matchhash == str2hash(origin.substring(i, i + match.length()))) {
                return true;
            }
        }
        return false;
    }

    private static int str2hash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash *= 26;
            hash += (str.charAt(i) - 97);
        }
        return hash;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("ccaaac", "caaac"));
        System.out.println(isMatch("ccaaac", "abc"));
    }

}

BM算法

原理

BF 算法性能会退化的比较严重，而 RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈希算法并不简单

BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，滑动算法

在这个例子里，主串中的 c，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 c 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面

BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）

坏字符规则

BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的

我们从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）

字符 c 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较

坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配

当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于（下标，都是字符在模式串的下标）

第一次移动3位

c在模式串中不存在，所以 xi = -1，移动位数 n = 2 - (-1) = 3

第二次移动2位

a在模式串中存在，所以 xi = 0，移动位数 n = 2 - 0 = 2

好后缀规则

我们把已经匹配的我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u}，那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置

如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况

过度滑动情况：

当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况

所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串（c），是否存在跟模式串的前缀子串（c）匹配的

如何选择坏字符和好后缀：我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数

代码实现

坏字符：

如果我们拿坏字符，在模式串中顺序遍历查找，这样就会比较低效

可以采用散列表，我们可以用一个256数组，来记录每个字符在模式串中的位置，数组下标可以直接对应字符的ASCII码值，数组的值为字符在模式串中的位置，没有的记为-1

bc[97]=a

bc[98]=b

bc[100]=d

有重复的字母以后面的位置为准

package com.rubin.algorithm.charsetmatch;

/**
 * BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，滑动算法.
 * 我们本例只讲解坏字符算法
 *
 * T = O(N/M)
 * n:主串长度
 * m:模式串长度
 */
public class BoyerMoore {

    private static final int[] BC = new int[256];

    private static void generateBC(String match) {
        // 这里只负责处理英文字母 不负责汉字 空字符的处理
        char[] chars = match.toCharArray();
        for (int i = 0; i < BC.length; i++) {
            BC[i] = -1;
        }
        for (int i = 0; i < chars.length; i++) {
            int ascii = chars[i];
            BC[ascii] = i;
        }
    }

    public static int isMatch(String origin, String match) {
        generateBC(match);
        char[] originChars = origin.toCharArray(),
                matchChars = match.toCharArray();
        int m = originChars.length, n = matchChars.length;
        int i = 0;
        while (i <= (m - n)) {
            int j;
            for (j = n - 1; j >= 0; j--) {
                if (matchChars[j] != originChars[i + j]) {
                    break;
                }
            }
            if (j < 0) {
                return i;
            }
            i = i + (j - BC[originChars[i + j]]);
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("ccaaac", "caaac"));
        System.out.println(isMatch("ccaaac", "abc"));
    }

}

应用

BM算法比较高效，在实际开发中，特别是一些文本编辑器中，用于实现查找字符串功能

Trie树

原理

Trie 树，也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题

比如：有 6 个字符串，它们分别是：how，hi，her，hello，so，see，我们可以将这六个字符串组成Trie树结构

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起

其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点为叶子节点）

Trie树的插入

Trie树的查找

当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径

Trie 树是一个多叉树

我们通过一个下标与字符一一映射的数组，来存储子节点的指针

假设我们的字符串中只有从 a 到 z 这 26 个小写字母，我们在数组中下标为 0 的位置，存储指向子节点a的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，我们就在对应的下标的位置存储 null

当我们在 Trie 树中查找字符串的时候，我们就可以通过字符的 ASCII 码减去“a”的 ASCII 码，迅速找到匹配的子节点的指针。比如，d 的 ASCII 码减去 a 的 ASCII 码就是 3，那子节点 d 的指针就存储在数组中下标为 3 的位置中

代码实现

package com.rubin.algorithm.charsetmatch;

/**
 * Trie 树，也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题
 * 本示例只处理a-z26个英文字母
 *
 * 如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。构建 Trie 树的过程，需要扫
 * 描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。但是一旦构建成功之后，后续的
 * 查询操作会非常高效。每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，
 * 就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中
 * 查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度
 */
public class TrieTree {

    private TrieNode root;

    public TrieTree() {
        root = new TrieNode('/');
    }

    static class TrieNode {
        char data;
        TrieNode[] children;
        boolean isLeaf;

        public TrieNode(char data) {
            this.data = data;
            children = new TrieNode[26];
            isLeaf = false;
        }
    }

    public void insert(String text) {
        char[] textChars = text.toCharArray();
        TrieNode p = root;
        for (int i = 0; i < textChars.length; i++) {
            int j = textChars[i] - 97;
            if (p.children[j] == null) {
                p.children[j] = new TrieNode(textChars[i]);
            }
            p = p.children[j];
        }
        p.isLeaf = true;
    }

    public boolean isMatch(String pattern) {
        char[] patternChars = pattern.toCharArray();
        TrieNode p = root;
        for (int i = 0; i < patternChars.length; i++) {
            int j = patternChars[i] - 97;
            if (p.children[j] == null) {
                return false;
            }
            p = p.children[j];
        }
        if (p.isLeaf == false) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        TrieTree trieTree = new TrieTree();
        trieTree.insert("hello");
        trieTree.insert("her");
        trieTree.insert("hi");
        trieTree.insert("how");
        trieTree.insert("see");
        trieTree.insert("so");
        System.out.println(trieTree.isMatch("ho"));
        System.out.println(trieTree.isMatch("how"));
        System.out.println(trieTree.isMatch("howw"));
    }

}