KMP算法

󰃭 2016-08-16

KMP算法原理

背景与原理

KMP算法与ac自动机一样，以其发现者作为算法名称。同样的，作为字符串的匹配优化算法，他的着重点仍然在于减少对重复前缀或者后缀的匹配次数，从而提高搜索的效率。
和ac自动机一样，KMP算法也是用一个失败跳转的规则来快速跳转。不同的是，由于KMP针对的是单字串的匹配，他不需要ac自动机那样用字典树来进行跨字串的跳转，只需要跳转到本字串的其他字符。因此，在通常情况下，KMP的跳转甚至只需要用一个整数来记录失败跳转的位置。

实例分析

假设有模式串：abcdabd，有待匹配字串bbcabcdababcdabcdabde，我们来分析KMP算法的跳转。
首先第一步匹配，模式串第一位a与匹配串第一位b不能匹配，模式串后移一位：

b b c a b c d a b a b c d a b c d a b d e
|
a b c d a b d

同样模式串第一位a与匹配串第二位b不匹配，模式串继续后移直到能够匹配的状态：

b b c a b c d a b a b c d a b c d a b d e
* * * | | | | | | 
. . . a b c d a b d

此时，发现模式串最后一位d与匹配串不能匹配，那么这里就会出现这样一个问题：比较暴力的做法是模式串继续后移1位进行匹配，这样当然能够达到搜索的效果，但是由于他抛弃了之前匹配串的特性，效率显得比较低下；另外一种思路，根据之前匹配的结果，我们不再是向后简单的移动1位，而是移动到一个与之前匹配完全不相关的位置，从而加速匹配。
比如，我们可以采用一个补救的方法，假设数据串模式串中都是不同的字符，那么我们对于与字符串匹配上的这个区间(abcdab)内的所有字串不需要再次匹配，可以直接跳过。然而实际上匹配串中出现了重复的字串，为了防止漏检，我们需要计算一个补救值快速定位到重复位置，我们称之为跳转。
上例中，在d处匹配失败，我们先移动到d的位置，在向前移动到之前的重复字符a处：

b b c a b c d a b a b c d a b c d a b d e
* * * * * * * | | 
. . . . . . . a b c d a b d (+6-2)

实际上，我们可以根据后缀数组的最长相同前缀来进行跳转位置的计算。在匹配之前预先计算好所有的跳转位置的计算，那么我们可以快速跳转，缩短匹配时间。

实现

/* kmp.h */
#include <vector>
#include <iostream>

//比较规则，用来比较数据单元是否相同
class comparePolicy {
    virtual int comp(void *, void *) = 0;
};

template <typename T, class Policy>
class kmp {
public:
    kmp()
    : arrayOffset { nullptr }
    , arraySize { 0 }
    {}

    ~kmp() {
        if (arrayOffset) {
            delete []arrayOffset;
            arrayOffset = nullptr;
            arraySize = 0;
        }
    }

    void Create(T *array, int len) {
        if (arrayOffset) {
            delete []arrayOffset;
            arrayOffset = nullptr;
            arraySize = 0;
            arrayData = nullptr;
        }
        if ( len < 1) 
            return ;

        arrayOffset = new int [len] {};
        arraySize = len;
        arrayData = array;

        buildFail();
    }

    std::vector<int> Search(T * pVal, int iLen) {
        Policy p {};
        std::vector<int> vRet{};
        if (iLen < arraySize) {
            return std::move(vRet);
        }
        int pos = 0;
        for (; pos < iLen; ) {
            int subpos = 0;
            for (; subpos < arraySize; ) {
                if (p.comp(pVal + pos + subpos, arrayData + subpos) == 0) {
                    subpos++;
                }
                else {
                    break;
                }
            }
            if (subpos == arraySize) {
                //如果有匹配上的，我们借用最后一步的失配（实际上是一样的）
                vRet.push_back(pos);
                subpos--;
            }
            pos += subpos - arrayOffset[subpos];
            
        }

        return std::move(vRet);

    }

private:
    void buildFail() {
        //后缀列表，起始pos + len
        T *suffix = arrayData + 1;
        int suffix_len = arraySize - 1;
        Policy p {};
        arrayOffset[0] = -1;
        while (suffix_len > 1) {
            int pos = 0;
            //寻找最长匹配串长度
            while (p.comp(arrayData + pos, suffix + pos) == 0) {
                pos++;
                if (pos == suffix_len) {
                    break;
                }
            }
            if (pos == 0) {//不匹配
                arrayOffset[arraySize - suffix_len + 1] = 0;
                suffix++;
                suffix_len --;
            }
            else {
                //另外一种情况下，我们给他们加上匹配的长度位置
                for (int i = 1; i <= pos; ++i) {
                    arrayOffset[arraySize - suffix_len + i ] = i;
                }
                suffix += pos;
                suffix_len -= pos;
            }

        }

    }


private:
    T *arrayData;
    int *arrayOffset;
    int arraySize;
};

/* test.cpp */
int main() {
    class CharCompare : public comparePolicy {
    public:
        virtual int comp(void *a, void *b) {
            return *(char *)a - *(char *)b;
        }
    };

    char test[] = "abcdabc";
    char test_string[] = "abcdabcdabcdabcdabd abcd";

    kmp<char, CharCompare> kmp_sample {};
    kmp_sample.Create(test, strlen(test));
    auto result = kmp_sample.Search(test_string, strlen(test_string));
    
    cout << test_string << endl;
    for(auto k : result) {
        for(int i = 0; i < k; i++) {
            cout << "-";
        }
        cout << test << endl;
    }

    return 0;
}

得到的结果如下：

abcdabcdabcdabcdabd abcd
abcdabc
----abcdabc
--------abcdabc