字符串匹配算法分析

1. Bruce Force 字符串暴力匹配算法

最简单也是最朴素的算法，直接贴上代码

//text是待匹配的目标串，pattern为模式串。
//需要在目标串text中找到与模式串pattern相同的子串
int BruteForce(string text, string pattern){
    int lenT = text.size();
    int lenP = pattern.size();
    int i=0, j=0;
    for (i = 0; i <= lenT - lenP; ++i){
        //从目标串的第一个字符起开始匹配
        for (j = 0; j < lenP; ++j){
            /*将模式串与目标串逐一比较，如果中途不匹配，则退出循环，
            从主串的下一字符起，重新与模式的第一个字符比较*/
            if (t[i + j] != p[j]){
                break;
            }
        }
        if (j == lenP){
            //当模式串与目标串完全匹配后，返回第一个字符在目标串中的位置
            return i;
        }
    }
    //未成功匹配，返回-1
    return -1;
}

按照上面的例子，设目标串长度 N，模式串长度 M，则最坏情况下（每次都在模式串最后一个字符匹配失败）匹配的次数为 M(N-M+1)

由于在字符串匹配问题中，模式串长度M一般远小于目标串长度N，故该算法时间复杂度可以为 O(MN)

2. KMP 算法

BF算法效率不高，最主要原因是在匹配失败后，并没有从中吸取失败的经验，而是放弃这一次匹配，将目标串的字符后移一位继续匹配。

然而发生失配时，其实我们已经知道前面已匹配成功的几个字符了。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

为了做到这点，KMP算法加入了一个数据结构，用于记录模式串的前缀集合与后缀集合的交集中最长元素的长度，即所谓的 部分匹配表（Partial Match Table,PMT），也被称之为pmt数组，如下图的例子所示

部分匹配表

这样的部分匹配表 pmt[i]=k，可以方便地找到模式串第0至i位的子串中，有前k个字符（即前缀）和后k个字符（即后缀）相同。在匹配时，若模式串下标为m的元素失配，将模式串向右移动m-pmt[m-1]位（若首位失配，则后移1位）。即模式串的后缀已经匹配完了，而前缀和后缀相同，因此只需要把模式串前缀与刚才匹配的后缀对齐，继续向后比较就行。这样，目标串的指针不需要前移；模式串失配时，其指针保证前移位数尽可能小。这样，我们可以利用这个记录模式串特征的部分匹配表来跳过不必要的匹配，以加速整个匹配流程。

因此，KMP算法在最坏情况下的时间复杂度也为O(M+N).

发表回复