字符串匹配之KMP算法

KMP算法是由D.E.Knuth，J.H.Morris和V.R.Pratt于1969年夏天提出的字符串快速匹配算法. KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的.

下面将分以下几个部分对KMP算法进行介绍:

1. KMP算法的匹配过程
2. next数组的解释
3. next数组的求法
4. 代码实现

KMP算法的匹配过程

举例来说, 要判断主串”ABCDABEABCDABCDABDE”是否包含模式串”ABCDABD”, 匹配过程描述如下(索引均从0开始):

第一轮匹配, 从第一个字符开始, 依次对主串和模式串的字符进行比较, 发现在模式串第6位出现了”失配”情况, 如下图所示:

如果按照BF算法的思想, 下面需要使用主串的第二个字符’B’和模式串的第一个字符’A’ 进行比较, 但是通过”肉眼可见”, 这次比较是无意义的. 不止如此, 使用主串接下来的两个字符’C’和’D’和’A’比较也是无意义的:

但是如何把我们”肉眼可见”的结果告诉程序, 让程序能自动跳过这些无意义的匹配, 对于当前这个例子, 就是跳过主串中”BCD”三个字符, 直接从主串第五个’A’开始与模式串进行下一轮匹配.

当失配情况发生时, 由于失配位之前的字符已经比较过了, KMP就是要利用已经比较过的信息, 不要把”搜索位置”移回已经比较过的位置，而是继续把它向后移，这样就提高了效率( 但是不能保证可以跳过所有无比较意义的字符 ).

在这里需要引入一个和模式串P对应的数组next[], 告诉匹配程序当”失配”情况发生时, 可以跳过多少个无比较意义的字符. next[]数组的分析及求法将在下文给出. 对于当前这个例子, 先直接给出next[]数组如下:

p[]    = {A,B,C,D,A,B,D}
next[] = {0,0,0,0,1,2,0};

当模式串p[]中的p[i]处的字符发生”失配”情况时, 根据next[i-1]值, 按照下面的公式就可以算出需要向后移动的位数:

在上面描述的第一轮的匹配中, 在第6位发生了”失配”情况, 已匹配部分(ABCDAB)的字符数是6,在next数组中对应的值是next[6-1]=next[5]=2, 按照上面的公式, 需要将主串向后移动(6-2=4)位, 移动后的情况如下:

继续之前的匹配过程, 依次比较, 在第3位发生了”失配”情况, 已匹配部分(AB)的字符数是2, 在next数组中对应的值是next[2-1]=next[1]=0, 根据移位公式, 需要向后移动(2-0=2)位, 移动后的情况如下:

这里就遇到了上面所说过的情况, KMP可以跳过一些无意义的比较, 但是不能保证可以跳过所有无意义的比较 , 所以才会有其他又针对KMP进行了优化的字符串匹配算法.

这时第一位字符就已经不匹配了, 即已匹配的字符数为0, 根据公式需要向后移动一位, 移动后的情况如图:

跟第一轮匹配的情况相同, 在第7位发生了”失配”情况, 那么, 已匹配的字符数就是6, 且next数组中失配位对应的数是2, 按照上面的公式, 需要向后移动(6-2=4)位, 移动后的情况如下:

匹配成功.

next数组的解释

首先需要引入两个概念, 前缀和后缀. 这里直接借用网上相关文章的定义, “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合.

前缀和后缀的最大公共长度就是”前缀”和”后缀”的最长的共有元素的长度. 以”ABCDABD”为例:

• “A”的前缀和后缀都为空集，共有元素的长度为0；
• “AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
• “ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
• “ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
• “ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
• “ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
• “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

在KMP算法的匹配过程中, 在匹配至某一位失配时, 其实在失配位之前的字符都已经经过了一轮比较, 通过对模式串自身进行比较计算得到next数组, 就可以跳过那些必然不可能产生匹配的字符.

那么对于模式串”ABCDABD”而言, 为什么当最后一位’D’失配时, 可以直接后移4位进行比较呢?

next数组实际上表明了模式串的对称程度, 当依次比较到’D’失配时, 前面所有的字符都已经经过了一轮比较, 主串和模式串的前六个字符其实是相同的, 这时要注意到”ABCDAB”的最长公共前后缀是”AB”, 只有把比较的指针移动一个前缀”AB”与后缀”AB”的距离才能避免没有意义的比较(参见本文第1,2,3张图).

next数组的求法

根据上对next数组的解释, next[i]表示已匹配的长度为(i+1)字符串的最大前后缀公共长度.

同样, 举出一个示例来说明next数组的求法. 下面模拟了一个for循环求出字符数组p[] = “agctagcagctagct”的next数组:

• i = 0时, p[0] = a, 无前后缀, 所以next[0] = 0;
• i = 1时, p[0…1] = ag, p[0] = a, p[1] = g, 不相等, 所以next[1] = 0;
• i = 2时, p[0…2] = agc, 由于next[1] = 0, 所以需要比较p[2]和p[0], p[2] = c, p[0] = a, 不相等, 所以next[2] = 0;
• i = 3时, p[0…3] = agct, 由于next[2] = 0, 所以需要比较p[3]和p[0], p[3] = t, p[0] = a, 不相等, 所以next[3] = 0;
• i = 4时, p[0…4] = agcta, 由于next[3] = 0, 所以需要比较p[4]和p[0], p[3] = a, p[0] = a, 相等, 所以next[4] = 1;
• i = 5时, p[0…5] = agctag, 由于next[4] = 1, 表明前面已经存在一个长度为1的公共序列了, 所以只需要比较p[5]和p[1], p[5] = g, p[1] = g, 相等, 所以next[5] = next[4] + 1 = 2;
• i = 6时, p[0…6] = agctagc, 由于next[5] = 2, 表明前面已经存在一个长度为2的公共序列了, 所以只需要比较p[6]和p[2], p[6] = c, p[2] = c, 相等, 所以next[6] = next[5] + 1 = 3;
• i = 7时, p[0…7] = agctagca, 由于next[6] = 3, 表明前面已经存在一个长度为3的公共序列了, 所以只需要比较p[7]和p[3], p[7] = a, p[3] = t, 不相等, 但是前面存在一个长度为3的公共序列, 如果p[0…7]存在公共前后缀, 则这个公共前后缀的对称度必然要小于3, 也就是说字符串abc中必须要存在一个子对称, 但是next[2]=0,即abc并不存在一个对称, 所以需要将p[7]与p[0]比较, 相等, 所以next[7]=1;
• i = 8时, p[0…8] = agctagcag, 由于next[7] = 1, 表明前面已经存在一个长度为1的公共序列了, 所以只需要比较p[8]和p[1], p[8] = g, p[1] = g, 相等, 所以next[8] = next[7] + 1 = 2;
• i = 14时, p[0…14] = agctagcagctagct, 由于next[13] = 7, 表明前面已经存在一个长度为7的公共序列了, 所以只需要比较p[14]和p[7], p[14] = t, p[7] = a, 不相等, 但是前面存在一个长度为7的公共序列, 如果p[0…14]存在公共前后缀, 则这个公共前后缀的对称度必然要小于7, 也就是说在p[0…6] = agctagc中必然存在一个子对称, 之前已经求得next[6] = 3, 这时需要将这个对称之后的一位p[3]与p[14]比较, 相等, 所以next[14] = next[6] + 1 = 4;

总结上面的规律, 当要求next[i]时, 由于之前已经求出next[i-1]的值, 表明前面p[0…(i-1)]的字符串的最长公共前后缀长度为next[i-1], 这时就需要分别讨论:

• 当 p[i] 等于 p[next[i]]时, 如下图所示, 红色部分表示前面已经成立的对称, 这时如果绿色的部分相等, 说明next[i]=next[i-1]+1;

• 当 p[i] 不等于 p[next[i]]时; 需要在前面已经成立的对称中递归寻找长度更小的对称, 然后比较找到的更小对称的后一位与p[i]的相等性, 即比较p[i] 和 p[next[next[i-1]]-1] 的相等性, 直到对称度为0, 表明确实不存在对称, 那么next[i]=0;

上图第一行中当C和F不相等时, 需要在前面的ABA中寻找子对称, 假如对称情况如第二行所示, 那么需要比对F和B的相等性, 如果相等, 则next[i]的值等于A的长度+1, 否则还要继续在A块中寻找子对称, 一直递归到前面的块不存在子对称为止.

代码实现

//
//  main.cpp
//  KMP
//
//  Created by XB on 2016/12/15.
//  Copyright © 2016年 Miu. All rights reserved.
//

#include <iostream>
#include <string>
using namespace std;
#define NO_MATCH -1

int *getNext(string const p)
{
    int length = (int)p.size();
    int *next = new int[length];
    next[0] = 0;
    for (int i = 1; i < length; i++) {
        //k为前面的对称长度
        int k = next[i-1];

        while (p[i] != p[k] && k!=0) {
            k = next[k-1];
        }
        if (p[i] == p[k]) {
            next[i] = k + 1;
        }else
        {
            next[i]= 0;
        }

    }
    return next;
}

int kmp(string const t, string const p, int *next)
{
    int i = 0;
    int j = 0;
    while (i < t.length()) {
        if (p[j] == t[i]) {
            //继续往后匹配
            j++;
            i++;
            if (j == p.length()) {
                return (int)(i - p.length());
            }
        }else{
            if (next[j-1] == 0) {
                //后移一位
                i++;
                j = 0;
            }else{
                //公式:移动位数 = 已匹配的字符数(j) - 对应部分的匹配值(next[j-1])
                /*
                 当主串失配位为i时, 模式串失配位为j, 此时起始比较位为(i-j), 即本轮比较的起始索引
                 计算起始索引是因为移动位数是以起始索引为基准的
                 移位后的起始比较索引 i = (i-j) + (j-next[j-1]) = i - next[j-1]
                 */

                i -= next[j-1];
                j = 0;
            }
        }
    }
    return NO_MATCH;
}





int main(int argc, const char * argv[]) {

    string p = "ABCDABD";
    string t = "ABCDABEABCDABCDABDE";
    int *next = getNext(p);


    int index = kmp(t, p, next);
    if (index == -1) {
        cout << "匹配失败" <<endl;
    }else{
        cout << "匹配结果, 索引:" << index << endl;
    }
    delete [] next;
    return 0;
}