KMP算法

序言

KMP算法相较于朴素模式匹配算法（也称为Brute-Force算法）在时间复杂度方面有所提升，由原先的O((n-m+1)m)降低为O(n+m)，n和m分别是文本串长度和模式串长度。

在学习KMP算法过程中，对其中get_next函数代码有所疑惑，在查找资料后豁然开朗，在此做下记录，以便以后查看。

具体内容

get_next函数目的是为了求得next数组，该数组说明了当我们遇到模式串中字符与文本串中字符不匹配时，能够在尽量减少重复匹配次数的情况下，在何处继续进行匹配。

比如说，我们在第一次匹配完成后，发现模式串B中字符f与文本串A中字符x不匹配，按照朴素模式匹配算法，我们应当将模式串右移一位，继续进行单个字符的匹配，若仍有字符不匹配，则继续将模式串右移，直至匹配成功或遍历完字符串A仍未匹配成功。

但通过观察可得：

• 在第一次匹配时，前5个字符匹配成功，在字符串aabaa中，第一个字符a与与第三个字符b是不同的，这也就意味着我们在朴素模式匹配时，将模式串B右移2位进行匹配的操作是可以省略的，而第二个字符a与第一个字符a相同，但与第三个字符b是不同的，那么将模式串B右移1位进行匹配的操作也是可以省略的；

• 在字符串aabaa中，前缀aa和后缀aa是相同的，这也就意味着我们在朴素模式匹配时，将模式串右移3位后的，前两次匹配是可以省略的，可以从模式串B的第三个字符开始匹配；

总结：如果第k个字符匹配不成功，可观察前k-1个字符，里面是否具有相同的前后缀，如果存在的话，则可以省去许多右移和匹配的步骤，大大节省时间。因此，如果获得模式串每个位置前（包括该位置）字符串的最大相同前后缀长度就很重要，这可以使我们知道该将模式串右移到哪个位置，以及从第几个字符开始匹配。

---

next数组就存储了这个信息，而get_next函数就是为了求得next数组的。

void get_next(String S, int* next) {
    int i;              // 代表后缀末尾字符下标
    int j = 0;          // 代表前缀末尾字符下标 && 代表最大相同前后缀长度
    next[0] = 0;
    for (i = 1; i < S.size(); i++) {
        while (j > 0 && S[j] != S[i])
            j = next[j-1];      // ？
        if (S[j] == S[i]) j++;  // 匹配成功需要将相同前后缀长度加1
        next[i] = j;
    }
}

比较难理解的就是这段代码内注释打问号的部分，为什么j是回溯到next[j-1]的位置呢？
通过下面几张图来进行解释。

其中，红色部分是已经匹配成功的前缀和后缀，a和b是下一个要匹配的字符，我们发现其不相同，那么按照get_next函数，我们应该跳转到j=next[j-1]的位置在进行匹配，而这个位置，其实是**B[模式串前j-1个字符的最长相同前后缀长度]**，字符串B的下标是从0开始的；

因为红色部分是相同的，所以对其再找最长相同前后缀，就相当于对红色部分进行分割，而因为寻找的是相同的前后缀，所以此时分割后的四个红色区域都是相同的；

如果此时j下标的字符和i下标的字符匹配，则可以直接将j加1来作为最长相同前后缀长度，若仍然不相同，则继续当前的操作，直到j变为0。

这样就可以清楚我们为什么需要回溯到j=next[j-1]的位置在匹配了，目的是为了利用先前已经匹配成功的相同前后缀长度，来获得最长相同前后缀长度。

Donate