KMP理论概要

KMP字符串匹配算法是一种效率更高的字符串匹配算法。相比于传统算法，由于其主串指针不需要回溯，因此大大减少了匹配需要的时间。

首先，让我们看看其是如何减少重复的步骤的：

假如有一字符串S：

我们想要让字符串“aaba”与其匹配。

那么，匹配看起来就是这样：

第一次匹配：

此时指针回退，主串指针回退至2，模式串回退至1。

第二次匹配：

此时主串指针再次回退。

可以看出，我们的主串指针在匹配过程中一直在重复读取某一段内容，这是大大有损效率的。若是能使主串指针不回退，只控制模式串指针回退一段距离，这也许可以改善。

实际上，第二次匹配可以简化为：

然后是第三次匹配：

那么，如何算出模式串指针应当回退多少呢？

根据KMP算法的核心思想，模式串T拥有一个对应表，用于记录模式串T重复的部分。

观察以下两个对应表：

可以看出，1号表格中，在匹配到第8个位置时，若是不匹配，只需要回到4对应的位置继续匹配就可以了，但是2号表格中，每一次匹配都必须要回到位置1重新匹配。

原因在于此：

可以看到，若是第8个字符不匹配并不影响前3个字符已经匹配成功的事实。因为5、6、7三个字符与1、2、3无异。既然我们已经匹配过a、b、c三个字符了，何必再匹配一次？

举例说明：

匹配 “aabaaaabcaabaaaba”与“aabaaaba”

可以看到，由于我们已经在匹配5、6、7三个字符时确定a、a、b三个字符是匹配的，那么我们就不需要在匹配前三个字符上浪费时间了。

那么，我们已经知道了如何使用模式串的“特性数组”来减少匹配重复字符上的浪费，但是这个数组怎样计算出来呢？

综合来看，我们计算此数组的目的就在于减少重复匹配，那么此数组的最大目的就是找出在制定字母之前有多少重复部分。

如：aabaaaba

由此，推导程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

std::vector<int> getNext(std::string in) {
        std::vector<int> res(in.length() + 1);
        int i = 1, j = 0;
        res[1] = 0;
        while (i < in.length()) {
            if (j == 0 || in[j - 1] == in[i - 1]) {
                i++;
                j++;
                res[i] = j;
            } else
                j = res[j];
        }
        return res;
    }

KMP再优化：

我们已经看出KMP算法是如何减少重复匹配来减少匹配时间的。但是，是否有一种更优化的方法呢？

观察以下字符串：