字符串匹配算法

一、BF算法

1. BF算法

BF（Brute Force）算法又叫作暴力匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。

在开始讲解这个算法前先定义两个概念：主串和模式串

• 如果我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串

• 我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。

2. 算法思想

BF 算法的思想就是，我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。如下图所示。

从图中可以看出，在极端情况下，比如主串是“aaaaa…aaaaaa”，模式串是“aaaaab”。我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。

不过，虽然 BF 算法的时间复杂度很高，但在实际的开发中却是一个比较常用的字符串匹配算法，原因有两点：

• 实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长，且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符时就可以就停止了，不需要把m个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但大部分情况下，算法执行效率要比这个高很多。

• 暴力匹配算法思想简单，代码实现也非常简单。在工程中，在满足性能要求的前提下，简单是首选。

3. 代码实现

public static int bf(String main, String pattern) {
    int n = main.length();
    int m = pattern.length();
    // 主串
    char[] mainArray = main.toCharArray();
    // 模式串
    char[] patternArray = pattern.toCharArray();
    // 遍历子串
    for (int i = 0; i <= n - m; i++) {
        int k = 0;
        // 遍历模式串中的每个字符看是否匹配子串
        for (int j = 0; j < m; j++) {
            if (mainArray[i + j] == patternArray[j]) {
                k++;
            } else {
                break;
            }
        }
        if (k == m) {
            return i;
        }
    }
    return -1;
}

二、RK算法

1. RK算法

RK（Rabin-Karp）算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。这个算法理解起来也不难，它其实就是 BF 算法的升级版。

在 BF 算法中，如果主串长度为 n，模式串长度为 m，那在主串中就会有 n-m+1 个长度为 m 的子串，我们只需要暴力地对比这 n-m+1 个子串与模式串，就可以找出匹配的子串。但每次检查主串与模式串是否匹配，都需要依次比对每个字符，所以 BF 算法的时间复杂度是 O(n*m)。

2. 算法思想

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

不过，通过哈希算法计算子串的哈希值时，我们仍需遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但算法整体效率并没有提高。有没有方法可以提高哈希算法计算子串哈希值的效率呢？

3. 优化点

1. 如何提高哈希算法计算子串哈希值的效率？

这需要哈希算法设计的非常有技巧。假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，然后把这个 K 进制数转化成十进制数作为子串的哈希值。

假设要处理的字符串只包含 a～z 这 26 个字符，那我们就用二十六进制来表示一个字符串。即把 a～z 这 26 个字符映射到 0～25 这 26 个数字上。在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，计算哈希值的时候，我们只需要把进位从 10 改成 26 就可以了。

这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。

从图中我们可以很容易的得出这样的规律：相邻的两个子串 **s[i-1] **和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值的计算公式是有交集的，因此我们可以用 s[i-1] 的哈希值很快的计算出 s[i] 的哈希值。

通过该公式，我们在计算每个子串的哈希值时，就不需要再遍历子串中的每个字符了，通过前一个子串的哈希值就能很快的计算出当前子串的哈希值了，所以在检查主串与模式串是否匹配这一过程，提高了很大的效率。

2. 通过哈希表进一步优化

针对 26m-1 这部分的计算，我们可以通过查表的方法来提高效率。我们事先计算好 260、261、262……26m-1，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。当我们需要计算 26 的 x 次方时，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

4. 复杂度

整个 RK 算法包含两部分：计算子串哈希值和模式串哈希值与子串哈希值之间的比较。

第一部分可通过设计特殊的哈希算法，使得扫描一遍主串就能计算出所有子串的哈希值，所以这部分时间复杂度是 O(n)。

第二部分直接比较的哈希值，单个比较操作的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。

5.问题处理

1. 计算哈希值时整型溢出怎么办？

当模式串很长时，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？实际上，我们为了能将哈希值落在整型数据范围内，可以牺牲一下，允许哈希冲突。比如我们可以把字符串中每个字母对应的数字相加，最后得到的和作为哈希值，而不是转换为二十六进制。这样产生的哈希值的数据范围就相对要小很多了。

2. 哈希冲突怎么办？

当存在哈希冲突时，有可能子串和模式串的哈希值是相同的，但其实两者是并不匹配的。实际上，解决方法很简单。当我们发现一个子串的哈希值跟模式串的哈希值相等时，我们只需要再对比一下子串和模式串本身是否匹配就好了。所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。

6. 代码实现

/**
 * RK算法，假设字符串中的每个字符都是a～z
 * 每个字符对应整数0～25，采用二十六进制计算哈希值
 *
 * @param main 主串
 * @param pattern 模式串
 */
public static int rk(String main, String pattern) {
    int n = main.length();
    int m = pattern.length();
    // 保存子串的哈希值
    int[] hash = new int[n - m + 1];
    int[] table = new int[26];
    // 主串
    char[] mainArray = main.toCharArray();
    // 模式串
    char[] patternArray = pattern.toCharArray();

    // 用哈希表保存计算好的平方值，空间换时间策略
    int number = 1;
    for (int i = 0; i < table.length; i++) {
        table[i] = number;
        number *= 26;
    }
    // 循环计算每个子串的哈希值
    for (int i = 0; i <= n - m; i++) {
        int hashcode = 0;
        for (int j = 0; j < m; j++) {
            hashcode += (mainArray[i + j] - 'a') * table[m - 1 - j];
        }
        hash[i] = hashcode;
    }
    // 计算模式串的哈希值
    int patternHashcode = 0;
    for (int i = 0; i < m; i++) {
        patternHashcode += (patternArray[i] - 'a') * table[m- 1 - i];
    }
    // 遍历判断哈希值是否相等
    for (int i = 0; i < n - m + 1; i++) {
        if (hash[i] == patternHashcode) {
            return i;
        }
    }
    return -1;
}

三、BM算法

1. BM算法

实际上，在某些极端情况下，BF 算法性能会退化的比较严重，而 RK 算法需要用到哈希算法，但设计一个可以应对各种类型字符的哈希算法并不简单。对于工业级的软件开发来说，我们希望算法尽可能的高效，并且在极端情况下，性能也不要退化的太严重。而 BM（Boyer-Moore）算法就是一种非常高效的字符串匹配算法。

2. 核心思想

我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。  

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

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

3.原理分析

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来看，这两个规则分别都是怎么工作的。

1. 坏字符规则

之前在匹配字符时，我们是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。

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

模式串中不存在坏字符 我们拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是 c 与模式串中的任何字符都不匹配。此时我们可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。

模式串中存在匹配的坏字符 滑动以后，模式串中最后一个字符 d 还是无法跟主串中的 a 匹配。但因为，此时坏字符 a 在模式串中是存在的，模式串中下标为 0 的位置也是字符 a。所以在这种情况下，我们不能直接把模式串往后滑动三位，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

第一次不匹配的时候，我们滑动了三位，第二次不匹配的时候，我们将模式串后移两位，那具体滑动多少位是怎么决定的呢？当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。

**注意，如果坏字符在模式串里出现了多次，那我们在计算 xi 的时候，要选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。**  

利用坏字符规则，BM 算法在最好情况下的时间复杂度是 O(n/m)。比如主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。不过只使用坏字符规则是不够的。因为根据 si-xi 计算出来的移动位数有可能是负数（下面会讲到为什么会是负数），比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还可能倒退。所以 BM 算法还需要用到好后缀规则。

2. 好后缀规则

好后缀规则实际上跟坏字符规则的思路是很类似的。当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。那此时该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计算模式串的滑动位数，不过我们也可以使用好后缀处理规则。

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

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

其实，如果我们直接将模式串滑动到主串 {u}的后面的话，是会有一定风险的。如下图所示，bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串 {u*}，但如果我们将模式串移动到好后缀的后面，就会错过模式串和主串可以匹配的情况。

如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的 {u} 与模式串有重合，那肯定就无法完全匹配，因为模式串中不存在 {u}。但当模式串滑动到前缀与主串中 {u} 的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。

如果好后缀的后缀与模式串的前缀相匹配，怎么办？ 以上图为例，bc 是好后缀，且模式串中不存在可匹配的 {u*}，那在模式串滑动过程中，只要模式串与主串重合的部分包含 {u}，那就肯定不能匹配。因为 bc 是好后缀，所以 {u} 的后缀只有一个 c。我们拿这个好后缀中的 c 去匹配模式串中的前缀，因为 {u} 的后缀只有一个字符，所以我们也只取模式串中的第一个字符，发现是相等的，所以这种情况下是有可能匹配的，所以我们移动模式串到 c 的位置。

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

●后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。 ● 前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。

我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是 {v}，然后将模式串滑动到如图所示的位置，对应上面那个例子就是 c 的位置，{u} 是 bc，{v} 是 c。

当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

4.实现思路

1. 坏字符规则实现思路

当遇到坏字符时，要计算往后移动的位数 si-xi，其中 si 是坏字符在模式串中的下标（从0开始），xi 是最靠右的匹配主串的坏字符在模式串中的下标。xi 的计算是重点，那如何查找主串中的坏字符在模式串中出现的位置呢？如果直接拿主串中的坏字符在模式串中顺序遍历查找，这样就会比较低效。但如果我们将模式串中的每个字符及其下标都存到散列表中，key为字符，value为下标，这样就能快速找到坏字符在模式串的位置下标了（经典的空间换时间策略）。

关于这个散列表，我们只实现一种最简单的情况，假设字符串的字符集不是很大，每个字符长度是 1 字节，我们用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。

如果将上面的过程翻译成代码，就是下面这个样子。其中，变量 b 是模式串，m 是模式串的长度，bc 表示刚刚讲的散列表。

private static final int SIZE = 256;

private void generateBC(char[] b, int m, int[] bc) {
    for (int i = 0; i < SIZE; ++i) {
        // 初始化bc
        bc[i] = -1;
    }
    for (int i = 0; i < m; ++i) {
        // 计算b[i]的ASCII值
        bc[b[i]] = i;
    }
}

掌握了坏字符规则之后，我们先把 BM 算法代码的大框架写好，先不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况。（因为哈希表记录的是不同字符在模式串中最后出现的位置，并不是 si 的位置往前查找的第一个位置，所以可能会出现 xi 大于 si 的情况。）  

public int bm(char[] a, int n, char[] b, int m) {
    // 记录模式串中每个字符最后出现的位置
    int[] bc = new int[SIZE];
    // 构建坏字符哈希表
    generateBC(b, m, bc);
    // i表示主串与模式串对齐的第一个字符
    int i = 0;
    while (i <= n - m) {
        int j;
        // 模式串从后往前匹配
        for (j = m - 1; j >= 0; --j) {
            // 坏字符对应模式串中的下标是j
            if (a[i+j] != b[j]) {
                break;
            }
        }
        // 匹配成功，返回主串与模式串第一个匹配的字符的位置
        if (j < 0) {
            return i;
        }
        // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
        i = i + (j - bc[(int)a[i+j]]); 
    }
    return -1;
}

2. 好后缀规则实现思路

好后缀规则的实现要比坏字符规则复杂一些，好后缀的处理规则中最核心的内容是：

●在模式串中，查找跟好后缀 {u} 匹配的另一个子串 {u*} ●在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串 {v} 匹配的后缀子串

在不考虑效率的情况下，这两个操作都可以用暴力匹配查找的方式解决。那有没有更高效的方式来处理呢？因为好后缀也是模式串本身的后缀子串，所以，我们可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。  

我们先来看，如何表示模式串中不同的后缀子串呢？因为后缀子串的最后一个字符的位置是固定的，下标为 m-1，我们只需要记录长度就可以了。通过长度，我们可以确定一个唯一的后缀子串。

现在，我们要引入最关键的变量 suffix 数组。suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀 {u} 相匹配的子串 {u*} 的起始下标值。

但是，如果模式串中有多个子串跟后缀子串 {u} 匹配，那 suffix 数组中该存储哪一个子串的起始位置呢？为了避免模式串往后滑动得过头了，我们肯定要存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。不过，这样处理就足够了吗？  

实际上，仅仅是选最靠后的子串片段来存储是不够的。我们再回忆一下好后缀规则。我们不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。  

如果我们只记录刚刚定义的 suffix，实际上，只能处理规则的前半部分，即在模式串中，查找跟好后缀匹配的另一个子串的位置。所以，除了 suffix 数组之外，我们还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。

现在，我们来看下，如何来计算并填充这两个数组的值？这个计算过程非常巧妙。  

我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。

我们把 suffix 数组和 prefix 数组的计算过程，用代码实现出来，就是下面这个样子：

// b表示模式串，m表示长度，suffix，prefix数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
    // 初始化
    for (int i = 0; i < m; ++i) {
        suffix[i] = -1;
        prefix[i] = false;
    }
    for (int i = 0; i < m - 1; ++i) { // b[0, i]
        int j = i;
        // 公共后缀子串长度
        int k = 0;
        // 与b[0, m-1]求公共后缀子串
        while (j >= 0 && b[j] == b[m-1-k]) {
            --j;
            ++k;
            // j+1表示公共后缀子串在b[0, i]中的起始下标
            suffix[k] = j+1;
        }
        // 如果公共后缀子串也是模式串的前缀子串
        if (j == -1) {
            prefix[k] = true;
        }
    }
}

有了这两个数组之后，我们现在来看，在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？  

假设好后缀的长度是 k。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理。

好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。

如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位。

5. 代码实现

至此，好后缀规则的代码实现也讲完了。我们把好后缀规则加到前面的代码框架里，就可以得到 BM 算法的完整版代码实现。

// a,b表示主串和模式串；n，m表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
    // 记录模式串中每个字符最后出现的位置
    int[] bc = new int[SIZE];
    // 构建坏字符哈希表
    generateBC(b, m, bc);
    int[] suffix = new int[m];
    boolean[] prefix = new boolean[m];
    generateGS(b, m, suffix, prefix);
    // j表示主串与模式串匹配的第一个字符
    int i = 0;
    while (i <= n - m) {
        int j;
        // 模式串从后往前匹配
        for (j = m - 1; j >= 0; --j) {
            // 坏字符对应模式串中的下标是j
            if (a[i+j] != b[j]) {
                break;
            }
        }
        // 匹配成功，返回主串与模式串第一个匹配的字符的位置
        if (j < 0) {
            return i;
        }
        int x = j - bc[a[i+j]];
        int y = 0;
        // 如果有好后缀的话
        if (j < m-1) {
            y = moveByGS(j, m, suffix, prefix);
        }
        i = i + Math.max(x, y);
    }
    return -1;
}

// j表示坏字符对应的模式串中的字符下标; m表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
    // 好后缀长度
    int k = m - 1 - j;
    if (suffix[k] != -1) return j - suffix[k] +1;
    for (int r = j+2; r <= m-1; ++r) {
        if (prefix[m-r]) {
            return r;
        }
    }
    return m;
}

四、KMP算法

1. KMP算法

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

KMP 算法的核心思想跟 BM 算法非常相近。我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符时，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。类比 BM 算法，在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。

与 BM 算法不同，模式串与主串的匹配过程是从模式串的首字符开始的，当遇到坏字符的时候，我们就要把模式串往后滑动。在滑动的过程中，只要模式串和好前缀有上下重合，那前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。那我们如何能对这一过程进行高效比较呢？

KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？

实际上，我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是 {v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。

为了表述方便，我们把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

2. 如何求好前缀的最长可匹配前缀和后缀子串？

这个问题其实不涉及主串（因为好前缀是公共的），我们只需要通过模式串本身就能求解。所以，类比 BM 算法中的 bc、suffix、prefix 数组，KMP 算法也可以提前构建一个数组，用来存储模式串中的每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 **next **数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。

数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可匹配前缀子串的结尾字符下标。具体示例如下图所示：

以模式串前缀 abab 为例，abab 的后缀子串有 bab、ab 和 b，其中，最长可匹配前缀子串为 ab，所以取 ab 子串的结尾字符 b 所在的下标索引 1，因此 next[3]=1。有了 next 数组，我们很容易就可以实现 KMP 算法了。假设 next 数组已经计算好了，先给出 KMP 算法的框架代码。

/**
* a, b分别是主串和模式串；n, m分别是主串和模式串的长度
*/
public static int kmp(char[] a, int n, char[] b, int m) {
    int[] next = getNexts(b, m);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        // 一直找到a[i]和b[j]
        while (j > 0 && a[i] != b[j]) {
            j = next[j - 1] + 1;
        }
        if (a[i] == b[j]) {
            ++j;
        }
        // 找到匹配模式串的了
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

3. 失效函数计算方法

现在，我们来看下最复杂的部分，也就是 next 数组是如何计算出来的？我们可以用暴力求解的方法，比如要计算模式串 b 的 next[4]，我们就把 b[0, 4] 的所有后缀子串从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。但显然，这种方法的效率非常低，那有没有更加高效的方法呢？

实际上，这里的处理技巧类似于动态规划。我们按照下标从小到大，依次计算 next 数组的值。当我们要计算 next[i] 的时候，前面的 next[0]，next[1] …… next[i-1] 应该已经计算出来了。利用已经计算出来的 next 值，我们就可以快速推导出 next[i] 的值了。

如果 next[i-1]=k-1，即子串 b[0, k-1] 是 b[0, i-1] 的最长可匹配前缀子串。如果子串 b[0, k-1] 的下一个字符 b[k] 与 b[0, i-1] 的下一个字符 b[i] 匹配，那子串 b[0, k] 就是 b[0, i] 的最长可匹配前缀子串。所以，next[i] 等于 k。但是，如果 b[0, k-1] 的下一字符 b[k] 跟 b[0, i-1] 的下一个字符 b[i] 不相等呢？这个时候就不能简单地通过 next[i-1] 得到 next[i] 了。这个时候该怎么办呢？

我们假设 b[0, i] 的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉，那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然 b[0, i-1] 最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]，那么我们就可以考察 b[0, i-1] 的次长可匹配后缀子串 b[x, i-1] 对应的可匹配前缀子串 b[0, i-1-x] 的下一个字符 b[i-x] 是否等于 b[i]。如果等于，那 b[x, i] 就是 b[0, i] 的最长可匹配后缀子串。

可是，如何求得 b[0, i-1] 的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是，查找 b[0, i-1] 的次长可匹配后缀子串，这个问题就变成，查找 b[0, y] 的最长匹配后缀子串的问题了。

按照这个思路，我们可以考察完所有的 b[0, i-1] 的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i] 就是 b[0, i] 的最长可匹配后缀子串。

4. 复杂度分析

1. 时间复杂度

KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，我们要分别从这两部分来分析。

在第一部分计算 next 数组的代码中，第一层 for 循环中 i 从 1 到 m-1，for 循环内部还有一个 while 循环，如果我们能知道每次 for 循环、while 循环平均执行的次数，假设是 k，那时间复杂度就是 O(k*m)。但是，while 循环执行的次数不怎么好统计，所以我们放弃这种分析方法。我们可以找一些参照变量，i 和 k。i 从 1 开始一直增加到 m，而 k 并不是每次 for 循环都会增加，所以，k 累积增加的值肯定小于 m。而 while 循环里 k=next[k]，实际上是在减小 k 的值，k 累积都没有增加超过 m，所以 while 循环里面 k=next[k] 总的执行次数也不可能超过 m。因此，next 数组计算的时间复杂度是 O(m)。

在第二部分中，i 从 0 循环增长到 n-1，j 的增长量不可能超过 i，所以肯定小于 n。而 while 循环中的那条语句 j=next[j-1]+1 是不会让 j 增长的，因为 next[j-1] 的值肯定小于 j-1，所以 while 循环中的这条语句实际上也是在让 j 的值减少。而 j 总共增长的量都不会超过 n，那减少的量也不可能超过 n，所以 while 循环中的这条语句总的执行次数也不会超过 n，所以这部分的时间复杂度是 O(n)。

所以，综合两部分的时间复杂度，KMP 算法的时间复杂度就是 O(m+n)。

2. 空间复杂度

KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。

5. 代码实现

/**
* a, b分别是主串和模式串；n, m分别是主串和模式串的长度
*/
public static int kmp(char[] a, int n, char[] b, int m) {
    int[] next = getNexts(b, m);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        // 一直找到a[i]和b[j]
        while (j > 0 && a[i] != b[j]) {
            j = next[j - 1] + 1;
        }
        if (a[i] == b[j]) {
            ++j;
        }
        // 找到匹配模式串的了
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}


// b表示模式串，m表示模式串的长度
private static int[] getNexts(char[] b, int m) {
    int[] next = new int[m];
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < m; ++i) {
        while (k != -1 && b[k + 1] != b[i]) {
            k = next[k];
        }
        if (b[k + 1] == b[i]) {
            ++k;
        }
        next[i] = k;
    }
    return next;
}

五、有限状态自动机

1.定义

有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。

自动机(Automaton)：就是一个代码块,只做一件事——接收输入值，和状态值，输出同为状态值的结果。

有限(Finite)：是指自动机接收、输入的状态种类是有限的。

确定(Deterministic )：是指自动机的输出状态是单一的一个状态，不然就是NFA了。

2. 有限状态自动机

• FA会接收一个输入的字符串，输出YES/NO，即自动机 FA 会判断它能否识别输入的字符串

• 我们用形式化的元组M来描述这一功能

  • 字母表 ∑：给定的字符集（输入的符号）

  • 状态集 S：有限自动机状态（状态变量集合）。

  • 初始状态 q0：有限自动机初始状态，明确FDA的开始状态。必须要有开始状态，就像变量必须要有初始值，你才能执行动作。

  • 终结状态集 F：明确FDA的结束状态，产生最终的结果。正则表达式识别字符串，在扫描整个字符串过程中，FDA从开始到结束状态会有递归的过程。一旦到达结束状态，就会切换为开始状态读取下一个字符。

  • 转换函数 集δ：自动机在接收输入字符串后如何动作。

3. 分类

有限状态自动机分为 确定的有限状态自动机 和 非确定的有限状态自动机

非确定有限状态自动机与确定有限状态自动机的唯一区别是它们的转移函数不同。确定有限状态自动机对每一个可能的输入只有一个状态的转移。非确定有限状态自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。

4. 举例

确定的有限状态自动机示例(DFA)

我们来写一下上图中的元组M中的各元素：

• ∑ ={a,b}

• S = {0, 1, 2}

• q0 = 0

• F = {2}

• δ 转移函数：

  • { (q0, a) -> q1, (q0, b) -> q0,

(q1, a) -> q2, (q1, b) -> q1,

(q2, a) -> q2, (q2, b) -> q2 }

我们假设一个字符串"abab"传入，流程为

• 在节点 0 读取字符a 状态转移到节点1

• 在节点1 读取字符b 状态1保持

• 在节点1 读取字符a 状态转移到节点2

• 在节点2 读取字符b 状态2保持

不确定的有限状态自动机示例(NFA)

我们来写一下上图中的元组M中的各元素：

• ∑ ={a,b}

• S = {0, 1}

• q0 = 0

• F = {1}

• δ 转移函数：{(qo, a) -> {q0, q1},

(qo, b) -> {q1},

(q1, b) -> {q0, q1}}

5. DFA的实现

DFA的状态转移图本质上就是一个有向图，因此我们可以用表示有向图的数据结构来表示DFA，常用的有邻接表、邻接矩阵等。

6. 具体案例

问题：

验证给定的字符串是否可以转换为十进制数字。

存在于有效十进制数字中的字符列表：

• 数字 0-9

• 指数 "e"

• 正/负号 "+"/"-"

• 小数点 "."

示例：

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

思路：

可以从开始一个部分一个部分的判断，正负号 -> 数字 - > . -> 数字 -> e -> 正负号 -> 数字，中间注意数字状态与非数字状态的判断就行。

也可以用自动机来做，可以画出状态转移图如下：

注：认为 .3 或 3. 也是正确的数字

态转移可以用状态转移表表示：

这里不考虑首尾空格，可以减少一种状态

列首表示输入字符，行首表示当前状态，表格表示当前状态输入列首字符后转移到的状态。

状态\输入	'e'	'+'/'-'	'0'..'9'	'.'	other
0 start	end	signed	number	dot	end
1 signed	end	end	number	dot	end
2 dot	end	end	float	end	end
3 float	e	end	float	end	end
4 e	end	e_signed	e_number	end	end
5 e_number	end	end	e_number	end	end
6 number	e	end	number	float	end
7 e_signed	end	end	e_number	end	end
end	end	end	end	end	end

/**
 * 状态枚举
 */
enum class State {
    Start, // 开始
    Signed, // 正、负 符号
    Dot, // 点
    Number, // 数字
    Float, // 小数
    E, // e
    ESigned, // e符号
    ENumber, // e数字
    End // 结束
}


fun isNumber(s: String):Boolean{
    // 定义转移状态表
    val stateTable = mutableMapOf(
        State.Start to mutableListOf( State.End, State.Signed, State.Number, State.Dot, State.End),
        State.Signed to mutableListOf( State.End, State.End, State.Number, State.Dot, State.End),
        State.Dot to mutableListOf( State.End, State.End, State.Float, State.End, State.End),
        State.Number to mutableListOf( State.E, State.End, State.Number, State.Float, State.End),
        State.Float to mutableListOf( State.E, State.End, State.Float, State.Dot, State.End),
        State.E to mutableListOf( State.End, State.ESigned, State.ENumber, State.End, State.End),
        State.ESigned to mutableListOf( State.End, State.End, State.ENumber, State.End, State.End),
        State.ENumber to mutableListOf( State.End, State.End, State.ENumber, State.End, State.End),
    )

    // 定义初始状态
    var startState = State.Start

    // 获取输入数据的
    s.trim().toCharArray().forEach {it ->
        // 获取对应的输入列
        var inputColumn = 4
        if( it == 'e'){
            inputColumn = 0
        }else if(it == '+' || it == '-'){
            inputColumn = 1
        }else if(it.isDigit()){
            inputColumn = 2
        }else if(it == '.'){
            inputColumn = 3
        }else{
            inputColumn = 4
        }
        // 进行状态转移
        startState = stateTable[startState]?.get(inputColumn)!!
        // 如果结束
        if(startState == State.End){
            return false
        }
    }
    // 判断最终状态 ,只有如下三种状态才是数据
    return startState == State.ENumber || startState == State.Number || startState == State.Float
}

fun main() {
    println("%s => %s".format("0", isNumber("0")))
    println("%s => %s".format(" 0.1 ", isNumber(" 0.1 ")))
    println("%s => %s".format("abc", isNumber("abc")))
    println("%s => %s".format("1 a", isNumber("1 a")))
    println("%s => %s".format("2e10", isNumber("2e10")))
    println("%s => %s".format(" -90e3 ", isNumber(" -90e3 ")))
    println("%s => %s".format(" 1e", isNumber(" 1e")))
    println("%s => %s".format("e3", isNumber("e3")))
    println("%s => %s".format(" 6e-1", isNumber(" 6e-1")))
    println("%s => %s".format(" 99e2.5 ", isNumber(" 99e2.5 ")))
    println("%s => %s".format("53.5e93", isNumber("53.5e93")))
    println("%s => %s".format(" --6 ", isNumber(" --6 ")))
    println("%s => %s".format("-+3", isNumber("-+3")))
    println("%s => %s".format("95a54e53", isNumber("95a54e53")))
}

运行结果如下:

0 => true
 0.1  => true
abc => false
1 a => false
2e10 => true
 -90e3  => true
 1e => false
e3 => false
 6e-1 => true
 99e2.5  => false
53.5e93 => true
 --6  => false
-+3 => false
95a54e53 => false

六、字典树

1.树

树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构、等等。

树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树具有以下特点：

1. 每个结点有零个或多个子结点；

2. 没有父结点的结点为根结点；

3. 每一个非根结点只有一个父结点；

4. 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一棵子树；

2.字典树

什么是字典树

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

字典树的原则

1. 根节点不含字符

2. 根节点到某一终点连起来即为搜索字符串

3. 任意节点的所有子节点包含字符不同

字典树的查询规则

字典树的查找方法也很简单：

1. 每次从根结点开始搜索；

2. 获取关键词的第一个字符，根据该字符选择对应的子节点，转到该子节点继续检索；

3. 在相应的子节点上，获取关键词的第二个字符，进一步选择对应的子节点进行检索；

4. 以此类推，进行迭代过程；

5. 在某个节点处，关键词的所有字母已被取出，则读取附在该节点上的信息，查找完成。

字典树的分类

字典树又分为压缩字典树、非压缩字典树等，我们的AC自动机算法就是一棵典型的非压缩字典树。

3.字典树的实现

class Trie {

    // 根节点
    var root: TrieNode
    // 初始化
    init {
        root = TrieNode()
        root.wordEnd = false
    }

    /**
     * 插入字符串
     * @param word 字符串
     */
    fun insert(word: String){
        var node = root
        for (c in word.toCharArray()) {
            //判断该节点是否已存在
            if(!node.children.containsKey(c)){
                // 不存在将其加为子节点
                node.children[c] = TrieNode()
            }
            // 当前节点下移
            node = node.children[c]!!
        }
        // 最后的节点标记为叶子节点
        node.wordEnd = true
    }


    /**
     * 完整包含
     * @param word 待搜索字符串
     */
    fun search(word: String): Boolean{
        // 从根节点开始搜索
        var node = root
        for (c in word.toCharArray()) {
            // 开始搜索
            if(!node.children.containsKey(c)){
                // 节点不包含，直接结束
                return false
            }
            // 节点包含，当前节点下移
            node = node.children[c]!!
        }
        // 发现，并且是叶子节点，则找到
        return  node.wordEnd
    }


    /**
     * 前缀搜索
     * @param word 待搜索前缀
     */
    fun startWith(word: String): Boolean{
        // 从根节点开始搜索
        var node = root
        for (c in word.toCharArray()) {
            // 开始搜索
            if(!node.children.containsKey(c)){
                // 节点不包含，直接结束
                return false
            }
            // 节点包含，当前节点下移
            node = node.children[c]!!
        }
        // 发现，并且无需判读是否为叶子节点
        return  true
    }

    /**
     * 节点定义
     */
    class TrieNode {
        // 子节点
        var children: MutableMap<Char, TrieNode>
        // 是不是叶节点
        var wordEnd: Boolean
        init {
            children = mutableMapOf()
            wordEnd = false
        }
    }
}


fun main() {
    // 待匹配规则的字符串
    val trie = Trie()
    trie.insert("张三是法外狂徒")
    trie.insert("李四是个好人")
    trie.insert("今天天气真的好热")
    trie.insert("明天应该会下雨吧")

    // 进行匹配
    // 全文匹配
    println("完全匹配:%s -> %s".format("张三是法外狂徒",trie.search("张三是法外狂徒")))
    println("完全匹配:%s -> %s".format("法外狂徒",trie.search("法外狂徒")))
    println("完全匹配:%s -> %s".format("李四是个坏人",trie.search("李四是个坏人")))

    // 前缀匹配
    println("前缀匹配:%s -> %s".format("张三是法",trie.startWith("张三是法")))
    println("前缀匹配:%s -> %s".format("明天",trie.startWith("明天")))
    println("前缀匹配:%s -> %s".format("会下雨吧",trie.startWith("会下雨吧")))

}

测试结果:

完全匹配:张三是法外狂徒 -> true
完全匹配:法外狂徒 -> false
完全匹配:李四是个坏人 -> false
前缀匹配:张三是法 -> true
前缀匹配:明天 -> true
前缀匹配:会下雨吧 -> false

七、AC自动机

1. 什么是AC自动机

AC自动机(Aho-Corasick automaton)算法于1975年产生于贝尔实验室，是一种用于解决多模式匹配问题的经典算法。常被用来做敏感词检测，后处理的替换模块也是基于此。值得注意的是，AC自动机应当属于基于前缀搜索的非压缩字典树。

特点：

1. 基于非压缩字典树。

2. 多模式匹配，速度快且稳定。

3. 基于确定有限状态机(DFA)

2. 原理

1. 以模式串为his、hers、she、he为例，首先构建出一个字典树(trie):

看目前进行匹配会存在什么问题?

• his girl 能够匹配吗？

• Look his girl 能够匹配吗？

• shis 能够匹配吗？

1. 加入失败指针，为了节省匹配次数，不放弃已匹配过的部分，AC自动机之中加入了fail路径，又叫失败路径(指针)。失败指针能够在节点无法匹配下个字符的时候，转向其他节点。

来看目前进行匹配会存在什么问题？

• shis 能够匹配吗？

• look his girl 能够匹配吗？

1. 失败指针的构建

构建规则：

• root指向自己。

• father节点是root的指向root

• 其他节点回溯判断father节点的路径，如果father节点的fail能够接纳自己，则指向 father的fail节点接纳自己后的节点，否则继续回溯father节点的father节点的fail路径，如果回溯到根节点还是没有找到的话，那么就指向根节点。

(1) root指向自己

(2)father节点是root的指向root。

(3)回溯判断father节点的路径，如果father节点的fail能够接纳自己，则指向 father的fail节点接纳自己后的节点。

(4)否则继续回溯father节点的father节点的fail路径，如果回溯到根节点还是没有找到的话，那么就指向根节点。

1. 最终构建完毕，结果如下：

3. 尝试匹配

• 尝试匹配ushhis。

当前状态	输入字符	下一状态
0	u	0
0	s	7
7	h	8
8	h	1
1	i	2
2	s	3(terminal)

• 尝试匹配hep

当前状态	输入字符	下一状态
0	h	1
1	e	4(terminal)
4		0
4	p	0

• 尝试匹配 his girl

当前状态	输入字符	下一状态
0	h	1
1	i	2
2	s	3(terminal)
3		7
7	g	0
0	i	0
0	r	0
0	l	0

• 尝试匹配 look his girl

当前状态	输入字符	下一状态
0	l	0
0	o	0
0	o	0
0	k	0
0	h	1
1	i	2
2	s	3(terminal)
3		7
7	g	0
0	i	0
0	r	0
0	l	0

八、 基于AC自动机的领导人抽取算法

1. 领导人抽取模板

领导人抽取模板目前分为三个，分别为领导人列表，活动规则列表，活动规则和事件对应表。

领导人列表

杨卫东
宁云

活动规则列表

杨卫东????????????????出席????????主持
杨卫东????????????????会议????指出
在????????田间????????杨卫东
在????????田间????????宁云

活动规则和事件对应表

杨卫东????????????????出席????????主持	出席会议
杨卫东????????????????会议????指出	出席会议
在????????田间????????杨卫东	考察调研
在????????田间????????宁云	考察调研

2. AC自动机构建

1. 构建字典树

1. 构建fail路径

3.数据模板初始化

• 领导人名称初始化为List

• 模板初始化为AC自动机，并且保存好每个模板直接的？数量，具体如下

如：杨卫东????????????????出席????????主持

杨卫东 0

null 16

出席 0

null 8

主持 0

• 活动规则和事件对应表初始化为一个MAP

杨卫东????????????????出席????????主持 出席会议

杨卫东????????????????会议????指出 出席会议

在????????田间????????杨卫东 考察调研

在????????田间????????宁云 考察调研

4. 根据字符串匹配

例如输入字符串如下：

安吉县委书记杨卫东与昨日出席会议并主持了交流会。

1. 对输入的字符串按照字符进行分隔，如下:

安 吉 县 委 书 记 杨 卫 东 与 昨 日 出 席 会 议 并 主 持 了 交 流 会。

1. 每个字依次经过状态机，其转移状态如下。

当前状态	输入	下一状态
0	安	0
0	吉	0
0	县	0
0	委	0
0	书	0
0	记	0
0	杨	1
1	卫	2
2	东	3(输出状态)
0	与	0
0	昨	0
0	日	0
0	出	4
4	席	5(输出状态)
0	会	8
8	议	9(输出状态)
0	并	0
0	主	6
6	持	7(输出状态)
0	了	0
0	交	0
0	流	0
0	会	8

1. 统计各个输出的东西

输出内容	在字符串中的索引	长度	可以匹配的规则
杨卫东	8	3	杨卫东????????????????出席????????主持 杨卫东????????????????会议????指出 在????????田间????????杨卫东
出席	13	2	杨卫东????????????????出席????????主持
会议	15	2	杨卫东????????????????会议????指出
主持	18	2	杨卫东????????????????出席????????主持

1. 各个规则进行进行判断

首先去重统计现有的所有规则，得到了3条规则如下：

杨卫东????????????????出席????????主持

杨卫东????????????????会议????指出

在????????田间????????杨卫东

• 匹配第一条规则: 杨卫东????????????????出席????????主持

(1) 首先判断输出内容的集合是否包含规则的所有集合

[杨卫东, 出席, 会议, 主持] 包括 [杨卫东, 出席，主持]

(2) 校验规则是否满足

• 第一步，获取第一个节点所在的输出内容，及[杨卫东] 的输出内容，

• 第二步，根据中间？获取中间缺失的字符数量为 16。

• 第三步，在获取规则的下一个节点的输入内容，及[出席]的输出内容。

• 第四步，进行两个几点直接的匹配，具体匹配规则如下：

a. 获取当前节点， 获取上一个节点。

b. 获取当前节点的字符开始的地方，即为 字符串中的索引 - 字符长度。

c. 判断上一个节点的索引 + 缺失的字符数量 >= 开始的地方 并且 开始的地方 >= 上一个节点的索引。

d. 举例：

上一个节点 ： 杨卫东 8 3

最新节点: 出席 13 2

跳过的字符为 16

获取上一个节点的字符开始的地方，13 - 2 = 11

获取上一个节点的索引 + 缺失的字符数量 8 + 16 = 24

判断 24 >= 11 and 11 > 8 条件成立， 表示中间缺失的字符串在16个以内，匹配成功。

(3) 将当前节点作为上一个节点，在获取下一个节点，即 主持。重复计算。

(4) 都满足，则表示匹配成功。

(5) 根据上面第三个模板构建的map。取出该模板对应的活动内容为 出席会议

(6) 根据第一个领导人名称list中匹配出领导人名称 杨卫东。