KMP

KMP有什么用

KMP主要应用在字符串匹配上。

KMP的主要思想是「当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。」

所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
next数组也可理解为前缀表，前缀表有什么作用呢？
「前缀表是用来回溯的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。」

为了清楚的了解前缀表的来历，我们来看一个例子：

前缀表.png

如上图所示，模式串 "ACTGPACY",观察一下"Y"前面的字符串"ACTGPAC",最长相等前缀和后缀为"AC",而Y所对应的2，是匹配失败时，模式字串应该回溯的位置，也即，模式串字符'T'的位置2.具体来看一个示例：

KMP匹配.png

如上图，用字符串P="ACTGPACY",匹配字符串S="ACTGPACTGKACTGPACY"。在主串S[i]='T'时匹配失败，此时P匹配到P[j]='Y',对P[j]前的字符串最长相等前缀和后缀"AC",字串指针回退到P[2]='T'的位置，继续和主串匹配。

求解next数组

从上图中（前缀表）可以看出，就是计算当前字符前字符串相等的前缀的长度。这里有一个问题需要注意一下，就是next[0]=-1，为何这里会初始化为-1，而不是0？
当匹配失败时，只有模式字串的指针会回溯，而主串的指针时不变的（第一位匹配失败时除外，此时不前进指针就无法匹配了），因此，如果第一位就失配了，那么如果i不移动，j调到next[j]，也就是next[0]，假如还是0的话，则就永远不匹配，死循环。因此我们要让i在这种情况下，强行移动一格，将next[0]设为-1，然后判断条件： if(0 > j || S[i] == P[j]）,当j==-1时表示第一位匹配失败，此时就需要移动主串指针了。求解next数组具体代码如下:

int* buildNext(char* P) { // 构造模式串 P 的 next 表
    size_t m = strlen(P), j = 0; // “主”串指针
    int* N = new int[m]; // next 表
    int  t = N[0] = -1; // 模式串指针
    while (j < m - 1)
        if (0 > t || P[j] == P[t]) { // 匹配
            j++; t++;
            N[j] = t; // 此句可改进为 N[j] = (P[j] != P[t] ? t : N[t]);
        }
        else // 失配
            t = N[t];
    return N;

}

用next数组匹配的代码如下:

int match(char* P, char* S) { // KMP 算法
    int* next = buildNext(P); // 构造 next 表
    int m = (int)strlen(S), i = 0; // 文本串指针
    int n = (int)strlen(P), j = 0; //模式串指针
    while (j < n && i < m) // 自左向右逐个比对字符
        if (0 > j || S[i] == P[j]) // 若匹配，或 P 已移除最左侧
        {
            i++; j++;
        } // 则转到下一字符
        else
            j = next[j]; // 模式串右移（注意：文本串不用回退）
    delete[] next; // 释放 next 表
    return i - j;
}

时间复杂度分析

再来看一下时间复杂度， 假设文本串长度为n，模式串长度为m。

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，但之前还要单独生成next数组，时间复杂度是O(m)（next数组的实现代码将在后续文章中继续讲解），所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n * m)，所以「KMP在字符串匹配中极大的提高的搜索的效率。」

1.jpg