在计算机科学中,Knuth-Morris-Pratt 字符串查找算法(常简称为“KMP算法”)可在一个主“文本字符串”S内查找一个“词”W的出现位置。
此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符。
Wikipedia

面对字符串查找(string searching)问题: > 在某串 haystack 中,寻找串 needle 第一次出现的位置。

这个问题也被称作为”the needle in a haystack problem”,用在草垛中寻找针的感觉,来形容这个问题的难度。
needle in haystack

然而KMP很好地利用O(n+k)的时间复杂度解决掉了这个问题。其中,nhaystack的长度,kneedle的长度。
为了更好了解这个问题,我们先过一下朴素算法

Naive algorithm, 朴素算法

算法步骤

字符串搜索的朴素算法特别简单,也很直觉化。

  1. haystack中的每一个字符进行循环。在循环中,用needle中的每一个字符与haystack中的当前字符进行比较。
  2. 如果比较没有进行到needle的结尾,并且当前的两个字符并不匹配,说明以位置的haystack字符开头的匹配不成功;将循环中的起始字符后移一位,进入下一循环。
  3. 如果比较进行到了needle的结尾,说明我们在haystack中找到了一个匹配串needle
  4. 如果循环完美结束,说明haystack中并不包含串needle

通俗来讲这个算法的大意即是,从haystack中的每一个字符开始寻找needle

C++ 代码

    int naiveAlgo(char *haystack, char *needle) {
        int n = strlen(haystack);
        int m = strlen(needle);
        for (int i = 0; i < n; i++) {
            int j = 0;
            for (; j < m; j++) {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == m) return i;
        }
        return -1;
    }

算法分析

此算法的整体是一个循环嵌套结构。外层循环最多循环n次,内层循环最多循环m次。
所以粗略分析此算法的时间复杂度为 O(m*n)

KMP (Knuth-Morris-Pratt) algorithm, KMP算法

在自然语言搜索中,我们会发现以上朴素算法的实际运行效率其实很不错,因为很多情况下,内层循环刚刚搜索1到2个字符就可以从循环中break出来,进入外层循环的下一轮。
然而,在一些其他的领域中(比如基因序列搜索),我们就无法再寄期望于于这种情况。我们需要一个更快的算法解决这个问题。

KMP算法应运而生。

KMP算法的核心是基于这样一种思考。在我们的朴素算法中,内层循环break的条件是,当前的字符并不匹配。这时候我们如果按照朴素算法终止循环并且从haystack的下一个字符重新开始搜索的话,我们会放弃很大一部分的关键信息:从haystack[i]haystack[i + j]的字符串,全部被我们抛弃了(其中haystack[i]haystack[i + j]正是串needle的前缀,长度为j) KMP算法发现了这样一个事实,于是可以通过建立failure function【失败函数,一说覆盖函数(overlap function),部分匹配表(partial match table)】,利用这个failure function和当前的字符找到下一循环的最优匹配起始点。

Failure Function

我们以串 "ABAABABC"作为needle串进行分析。其所有前缀列出如下:

0: ""
1: "A"
2: "AB"
3: "ABA"
4: "ABAA"
5: "ABAAB"
6: "ABAABA"
7: "ABAABAC"

对如上列表中的每一项,我们要找出一个最长连续子串,这个子串既是此项的前缀,又是此项的子后缀。这样的串列表如下:

0: ""
1: ""
2: ""
3: "A"
4: "A"
5: "AB"
6: "ABA"
7: ""

对如上列表中的每一项的标号,我们定义函数failure,其值等于此串的长度。我们得出如下failure函数表:

0: 0
1: 0
2: 0
3: 1
4: 1
5: 2
6: 3
7: 0

拥有了failure函数表之后,我们即可判断对needle中的每一个前缀,其最大的部分匹配(partial match)。不仅如此,我们还拥有了每一个子串的后缀。最好部分匹配(best partial match)是failure(n),次好部分匹配(second best partial match)是failure(failure(n)),依次类推。

举如下例子进行解释:
假设我们当前的部分匹配串是"ABAABA",而haystack中下一个字符是'B'。然而needle需要的下一个字符是'C',不匹配发生了。
1. 此时,我们通过找寻failure(6),找到最好部分匹配结果是3,于是前缀/后缀"ABA"成为了当前的部分匹配串。
2. 此时,needle需要的下一个字符是'A';不匹配再次发生,此时我们通过找寻failure(3),找到次好部分匹配结果是1,于是前缀/后缀"A"成为了当前的部分匹配串。
3. 此时,needle需要的下一个字符是'B',与haystack中的下一个字符相同,字符匹配成功,双方进入下一个字符的比较。

KMP的算法思路基本如上。下面讨论failure函数是如何创建的。

Failure Function Construction

failure函数的创建利用自然语言描述很是繁杂。请直接看C++代码

    vector<int> F;
    void build_failure_function(const char* needle) {
        int m = strlen(needle);
        F.resize(m + 1);
        //F[0] = F[1] = 0, always true
        F[0] = F[1] = 0;
        for (int i = 2; i <= m; i++) {
            for (int j = F[i - 1]; ; j=F[j]) {
                if (needle[j] == needle[i - 1]) {F[i] = j + 1; break;}
                else if (j == 0) {F[i] = 0; break;}
            }
        }
    }

KMP算法实现

KMP算法的实现与我们构建failure函数的方式很是类似。每当我们遇到一个字符的不匹配之时,我们通过查failure函数表,找到最好部分匹配,尝试下一个字符的匹配。如果最好部分匹配的下一个字符匹配尝试仍然失败,通过failure函数表查询次好部分匹配,尝试下一个字符的匹配。依次类推。

KMP的C++代码如下。

    int KMP(char *haystack, char *needle) {
		int n = strlen(haystack),
			m = strlen(needle);
		if (m == 0) return 0; //if needle is empty, always return 0
		build_failure_function(needle);
		int i = 0, //now needle pointer
			j = 0; //now haystack pointer
		for (; j != n; ) {
			if (haystack[j] == needle[i]) { // characters match
				i++;
				j++;  //move forward the pointers
				if (i == m) return j - i;  // found a full match
			}
			// if a char mismatch happens, and the needle is in 
			// its beginning char then move forward the
			// haystack pointer
			else if (i == 0) j++;  
			// if a char mismatch happens, and the needle is not
			// in its beginning char, try the next best
			// partial match, using the failure function 
			// to find the next best partial match.
			else i = F[i];
		}
		return -1; //match not found
    }

算法分析

KMP算法的时间复杂度是O(n + k)
具体证明请访问英文维基百科KMP算法词条,参照失败函数构建时间复杂度搜索时间复杂度、以及算法整体时间复杂度

##Reference

  1. TopCoder Tutorial for String Searching
  2. Wikipedia Zh, KMP算法词条
  3. Wikipedia En, KMP算法词条