KMP

[TOC]

KMP

简述

KMP算法，即Knuth-Morris-Pratt算法，是实现字符串匹配问题的一种较为高效的算法，相比于传统的朴素模式字符串查找算法，即Brute-Force算法，它的优势在于能够显著的降低时间复杂度。即，将O(m*n)复杂度降为O(m+n)。在介绍KMP算法前，我们先简单介绍一下BF算法的原理。

BF算法（朴素字符串查找）

串的简单模式匹配算法Brute-Force（布鲁特-福斯，又称朴素的模式匹配算法）算法：将主串S的第一个字符和模式串T的第1个字符比较 若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 –1。其代码通过双指针原理实现也相对比较简单。

int indexBFmatch(char* Str, char* SubStr)
{
    int i, j;
    int lens = strlen(Str), sublens = strlen(SubStr);
    for (i = 0; i < lens - sublens + 1; i++)	//for (i = 0; *(Str + i) != '\0'; i++)
    {
        if (*(Str + i) == *SubStr)
            for (j = 0; j < sublens && *(SubStr + j) == *(Str + i + j); j++)
        if (j == sublens) return i;
        
        /*for (j = 0; *(SubStr + j) != '\0' && *(SubStr + j) == *(Str + i + j); j++);
        	if (*(SubStr + j) == '\0') return i;*/
    }
    return -1;       
}
//没有处理大小写无关的问题，如要处理，只需加一个大小写无关比较函数即可。

其缺点也很明显，存在两个循环，时间复杂度是O(m*n)，其本质原因是：当前匹配在找到不匹配的字符（失配）后，要将源串中下一次匹配开始位置移动一个位置（即要回溯），而未利用当前已取得匹配的信息，而导致算法时间复杂度增大，如下图，匹配过一次获取的信息可以帮助我们从①直通⑥从而省去不必要的步骤，极大减少时间复杂度。这也就是KMP算法的核心思想之一。

KMP算法

原理&&核心思想

源串称为主串，定义为S，当前匹配位置为 i ；目标串称为子串，也称模式串，定义为T，当前匹配位置为j。当前在S[i]和T[j] 失配，进行下一次匹配时：保证主串当前位置i不减小（不动或增1），即不回溯。不重置为上次匹配开始位置的下一位置；子串（即模式串）当前位置j视情况回溯至起始串位置（0），或子串中某一位置k。其中 0 ≤ k < j 。那么，现在问题就出现了，如何确定 j 回溯的位置 k 呢？

BBC ABCDAB ABCDABCDABDE 这两个字符串分别在D和‘ ’的位置失配了，而我们怎么用获取的信息只将 j 回溯呢？ ABCDABD 其实，这就涉及到前缀串和后缀串的问题了，如果主串在 i 以前的后缀串与子串在 j 以前的前缀串匹 配了，那是不是就可以把 j 回溯到匹配的前缀串的后一个位置。而我们知道，子串在 i 以前和主串也是匹配的，那是不是可以把子串在 j 以前的前缀串和后缀串进行匹配如果匹配上了就回溯 j 到相应位置。这个问题现在就转化为了求子串在某个位置前的前后缀匹配问题，因此我们可以构造一个next数组，用来记录子串第 j 个位置前的最大前缀串和最大后缀串匹配的位置。如子串ABCDABD，其next数组对应为{-1,0,0,0,0,1,2,0}，这里我们看 j = 6 的情况，即ABCDAB的前后缀串匹配，显然AB能与AB匹配，而且这两个分别为重合长度最长的前后缀串了，因此next[6] = 2。即将 j 回溯到2的位置也就是C的位置，然后继续与主串匹配。这里我们要注意next[0]，如果 j = 0时候失配，那我们直接将j++，i++继续匹配，这时候j = next[j]后再加一需要回到0的位置，因此，我们将next[0]置为-1。令k = next[ j ]（函数next用子串当前位置j来计算下次开始匹配位置k，k 与j 显然具有函数关系），则注意：（1）k值仅取决于子串本身而与待匹配的主串无关。（2）k值为子串从头向后及从j向前（不含j）的两个串的最大相同部分的长度。（3）这里的两部分子串可以有部分重叠的字符，**但不可以全部重叠，即k最大为 j -1 **。由于next数组与主串无关，则现在的问题就转化为了如何根据子串快速求next数组。

next数组的本质是字符串首尾的自匹配问题，因此同样可以用KMP算法的原理，因此，我们从中可以嗅到一些递推的味道。例如串ABCDABD我们已知的是next[0] = -1，我们把i置为next的递进下标，从0开始，j置为前缀串的匹配下标，从-1开始。当i没到子串结尾时进行递推循环，如果j为-1（起始位置的特殊判定以及上一个位置甚至连首字符串都不匹配）或者第j位置的字符和第i个位置的字符匹配了，就将i++，j++（下标递进）后next[j]置为i（即回溯位置），如果没有匹配就将j回溯至next[j]（失配则回溯的思想）然后继续匹配，继续循环。至此结束循环得到nexy数组，其代码实现如下：

void get_next(char SubStr[], int next[])
{  	
    int i=0, j=-1;
    next[0] = -1;
    while(SubStr[i]!=‘\0’){
		if(j==-1 || SubStr[i]==SubStr[j]){ //i是模式串递进的失配位置
        i++; 
        j++; 
        next[i]=j;              //i也是next的递进下标
      }
      else 
        j = next[j];         //若字符不同，则j值回溯到上一个值
	 }  
}

代码实现

经过前面的原理分析，代码实际上以及呼之欲出了，这里直接给出KMP算法的C语言实现。

int KMPindex(char str[], char substr[])
{
    int i = 0, j = 0, *next;
    next = (int*)malloc(sizeof(int) * strlen(substr) + 1);	//构造next数组
    get_next(substr, next);		//获取next数组
    while (str[i] != '\0' && substr[j] != '\0')
    {
        if (str[i] == substr[j])		//匹配成功继续匹配
        {
            i++;
            j++;
        }
        else 	//匹配失败，回溯j后，重新匹配（若j = 0则不回溯（next[0] = -1））
            j = 0 ? i++ : j = next[j];
    }
    free(next);		//注意防内存泄漏
    if (substr[j] == '\0') return i - j;	//返回index注意相比开头位置i多向后移了j位
    else return -1;
}

至此KMP算法就完全结束了，其只运用了一个while循环，用不回溯i指针的方法将时间复杂度成功缩短到了O(m+n)，除此之外值得一提的是next数组的计算实际上是个时间复杂度O(1)的过程，这也是KMP算法的核心。