KMP算法的详细分析

前言

    关于KMP算法的描述在网上可以说是多如牛毛，以前学习的时候也碰到过这个问题。只是一直对它的理解不够深刻。而在网上搜索了一通之后，发现大量的文章要么就是简单的说一下思路然后给一堆代码，要么就是纯粹讲理论，对于实际的实现没有任何帮助。自己在学习和实现整个算法的过程中也碰到过几个小的细节，被卡在那里很久。经过很久的揣摩才想清楚了一点，这里就把整个算法的思想和实现过程详细描述一下。希望能够带来一点帮助。

 

最初始的方法

    我们在讨论KMP算法之前，先从一个最原始的思路开始考虑。这是一个检查字符串是否匹配的问题。假定我们有一个源字符串t和需要匹配的模式串pattern。我们希望就是在字符串t里找到一个匹配模式串pattern的地方。我们有一种最简单直接的思路，就是每次去从头比较两个串，如果发现一旦中间有一个不同，则从目标串的后面一个开始，重新去和模式串从头开始比较。这个比较的过程如下图：

    从图中我们可以看到，在a的情况下，我们匹配了第一个字符，然后第二个不匹配，然后我们就从目标串的c字符开始，再来看模式串里第一个。在b图中，也不匹配，然后我们继续移动到目标串的下一个。一直到图c的情况下，我们发现它们匹配了。于是找到了一个完整的匹配结果，并可以将这个匹配的位置返回。

    按照这个思路，我们也可以很容易得到一个实现，其代码如下：

public static int search(String pat, String txt) {
    int m = pat.length();
    int n = txt.length();
    for(int i = 0; i <= n - m; i++) {
        int j;
        for(j = 0; j < m; j++) {
            if(txt.charAt(i + j) != pat.charAt(j))
                break;
        }
        if(j == m) return i;
    }
    return -1;
}

    在这个方法里，我们假定找到一个匹配的串，则返回和目标串匹配的第一个字符的索引，否则返回-1。整个过程还是很简单的。整个算法的执行时间复杂度为O(mn)，m,n分别为两个串的长度。这个方法好在足够简单直观。可是在一些比较大的文件里搜索模式串的话，还是可能会有一定的性能影响。那么，我们有没有可能改进一下算法来提高性能呢？

 

第一步的观察

    我们再结合一个实例来运行一下前面的代码看看：

    在前面示例里，当i为0的时候，我们的模式串j匹配到2的时候失败了。这样我们就匹配了前面两个字符AB。可是在算法里，接着从i=1这个位置开始。其实我们都已经看到了，既然前面两个字符是AB，我们再去从B来做比较都没什么意义了。因为它肯定不一样。其实我们完全可以直接跳过它。

    我们再从一个笼统的角度来考虑一下字符串匹配的算法。其实我们要比较一个目标串和模式串是否匹配，无非就有如下这么几种情况。一种就是一个字符都不匹配，就好比前面方法中我们模式串里第一个字符和目标串比较就发现不匹配。还有一种就是完全匹配，那就是我们一个个的比较过来，到最后，发现它们都符合，然后这就是我们所期望的结果。当然，更多的情况可能就是我们只是匹配了一部分结果，然后发现后面的不匹配了。假定我们的模式串长度为n，那么我们可能出现部分匹配的情况就有n-1个，比如说1个字符匹配，2个...n-1个匹配。对于一个都不匹配和完全匹配我们都好理解，反正一个个过来，从前面算法来看，就是一个直接的线性时间。它们几乎没有什么改进的地方。所以我们问题的重点就在于针对有一部分串匹配的时候，怎么来改进它使得算法的性能更佳。从前面的分析我们刚才也看到了，确实对于一些部分匹配的情况来说，有的比较很明显，我们可以直接跳过去的。现在的问题关键在于，这些情况是个什么样的规律呢？我们该怎么来跳过去？

进一步推导

    我们来看一个具体的匹配过程：

    假定我们的目标串T和模式串P匹配检查到如图的情景。这个时候，我们两个串中间前面5个字符是匹配的，就第6个不匹配。如果我们要寻找下一个去匹配的点，将P从头开始去和后面那个目标串的比较的话，第一个比较的是b，不行，我们可以直接跳过去。那我们再往后面看一点，下一个字符是a，和模式串的第一个匹配，再后面的两个字符ba也和模式串里接着的第二三个字符匹配。就好比如下的情况：

    实际上，针对这个情况，我们刚才发现前面的三个字符已经和目标串匹配了的。我们完全可以从模式串的第4个开始和目标串进行比较。而且前面几种情况我们跳过了是因为它们第一个字符就不匹配，可以根本不用比较，而这个的情况是有一部分字符是匹配的，可能在目标串的后面那一段和我们模式串的第三个字符以后的部分匹配。所以这部分我们是不能忽略的。

    唔...这个时候，我们好像发现一点点什么规律了。问题的关键在于我们前面匹配了一部分字符串，然后我们又用模式串去和匹配了的那部分做比较，选择一些我们两者覆盖的部分，然后再从后面进行比较。前面这个问题中覆盖的部分如下：

    这个覆盖很有意思，它是我们前面部分匹配串的结尾，同时又是和我们模式串的开头是相同的。和我们前面那种原始搜索的办法比起来，我们是希望跳过不需要的比较，同时也希望不能错过一些匹配的位置。假设我们从某个部分匹配的位置开始，模式串想对于开头的位置越近而且它们能够满足前面的开头和结尾匹配的条件的话，它们匹配的那部分也越长。所以严格来说，我们相当于找到一个最长而且相等的前缀和后缀。当我们找到这部分相等的部分时，我们就不需要从头再来比较了，而且也不需要像原来的算法中那样目标串退回到这一次第一个比较的字符的后面，而是直接继续往后面比较。比如说前面示例中我们发现了aba这个部分，那么后面目标串就只要看接着的字符是不是等于模式串中间的第4个就可以了。

    结合我们前面的这一段讨论，我们可以找到一个部分匹配串里如何往后面进行选择比较的规律了。我们只要针对各种部分匹配的情况来考察它们是否有是否相等的前缀和后缀，然后来选择进行比较就好办了。我们前面针对的各种部分匹配情况，不管是1个匹配还是n-1个字符匹配，这些匹配的串其实本质上就是模式串的一部分。这样看起来似乎和目标串到没什么关系了。按照我们前面的分析，在上个问题中，我们匹配了5个字符的时候，发现有3个字符的前缀和后缀是相等的。于是后面我们就从第4个开始继续进行比较。如果我们匹配的是4个，3个，或者其他的呢？既然这种情况是定死了的，我们只要推导出来各种情况，以后每次直接从匹配的部分往后比较不就可以了吗？这样看来，我们只要建立这么一个前后缀匹配串的表就好办了。我们先拿一个模式串来推导一下：

 

    在图中，我们将模式串ababaca和每次部分匹配的情况做了一个对比。对于每个匹配的情况，和模式串重合的部分表示相互涵盖的地方。图中字符串红色的部分表示模式串剩余的部分。在前面只有一个字符a的情况下，因为我们希望的是要有前缀和后缀，而对于这种情况，我们可以认为它们没有前缀和后缀，所以返回匹配的字符个数为0。假定我们也按照前面的对应某个字串它有多少涵盖的地方，设为M[i]的数组，很容易得到一个如下的表：

i	0	1	2	3	4	5	6
P[i]	a	b	a	b	a	c	a
M[i]	0	0	1	2	3	0	1

 

实现

    有了前面的充分讨论，我们可以考虑一下该怎么实现一个如下M[i]数组。在这个基础之上我们再考虑如何实现整个的算法。我们先来看第一部分。

前缀覆盖实现

    现在我们需要的是针对各种长度的字串来考虑实现。对于长度为1的字串来说，肯定结果为0, 可以直接跳过去。对于长度为2的来说呢？我们需要比较的是第2个元素和第1个是否相等，如果相等的话，则有一个覆盖的元素。假如我们前面已经找到覆盖的若干个元素了，在后面接着的那个元素又不匹配，那我们该怎么来调整和计算覆盖了的长度呢？这是这个问题里最关键的部分。以下图为例：

    假定我们用j来表示覆盖的字符长度，在前面已经覆盖了3个的情况下，我们看第4个的时候发现已经不匹配了。这个时候我们就需要回退j，这个j该回退到哪里好呢？从0开始？在这个问题中，我们还有一种情况是可能找到匹配覆盖的：

    这个场景比较有意思。在前面我们发现第4个不匹配的情况下，我们至少知道前面是已经匹配了3个的。我们需要的是从这3个里回退到某个点来比较后面一个字符和前面不匹配的。最有意思的地方在于，我们这里不又回到前面找覆盖的子问题吗？至少前面我们已经找出来3个的元素里覆盖的是1。这里就退到了1这个位置来和前面的做比较。更巧合的是1表示3个里覆盖了一个，那么以这个来继续往后面比较的元素它的索引也正好是1。和这种情况一致的场景如下图：

    在前面我们匹配了3个之后发现第4个不匹配了，然后跳到j = 1开始比较。这里正好又匹配上了。匹配上之后我们就不用再往后面退了，只需要在原来这个的基础上加1表示这种情况下匹配的字符个数。

    所以，上面总结起来就是这么一个过程，当我们匹配到某个字符，假设到第j个了。这时发现它不匹配，我们就将j回退到M[j - 1]，如果这个时候它和目标字符相同了，则表示这个长度匹配的字符串长度为M[j - 1] + 1。否则我们就继续往回退。我们这里不断回退肯定是一个循环。而退出这个循环的条件是j == 0或者M[j - 1]这个位置的字符和目标字符相等了。所以我们可以得到一个如下的实现代码：

 

public static int[] computePrefix(final String s) {
	int size = s.length();
	int[] result = new int[size];
	int j = 0;

	for(int i = 1; i < size; i++) {
		while(j > 0 && s.charAt(j) != s.charAt(i)) {
			j = result[j - 1];
		}
		if(s.charAt(j) == s.charAt(i)) {
			j++;
		}
		result[i] = j;
	}
	return result;
}

   现在，我们也已经明白为什么要费这么大的劲来算一个这样的结果数组。这个结果数组表示的是对应匹配到某个长度字串时它们的前后缀覆盖长度，也表示我们在模式串里进行下一个比较的索引。

总过程实现

    我们在前面的基础上实现完整的过程。这个过程的实现代码如下：

public static void kmp(String target, String pat) {
	int sourceLength = pat.length();
	int targetLength = target.length();
	int[] result = computePrefix(pat);
	int j = 0;
	for(int i = 0; i < targetLength; i++) {
		while(j > 0 && pat.charAt(j) != target.charAt(i)) {
			j = result[j-1];
		}
		if(pat.charAt(j) == target.charAt(i)) {
			j++;
		}
		if(j == sourceLength) {
			System.out.println("find at index " + (i - j + 1));
			j = result[j-1];
		}
	}
}

    它的过程和前面的依次遍历的一个区别在于每次我们在碰到一个不匹配的时候，就通过pat字符串的匹配表往后退。和前面的比起来，它不需要两个串都退回到开始。由于在循环里我们可能查找到多个匹配的结果。我们在后面把每次匹配的索引都打印出来了。

    所有完整的代码都放在附件里。

总结

    前面对KMP算法的过程和推导讨论了这么多。这个问题的本质上还是对所有部分匹配的情况建立一个前后缀覆盖的关系表。以后查询的时候可以通过这个表来决定匹配多少个字符的时候从哪个字符开始进行匹配。这样减少了目标字符串的回退，使得算法的性能得到比较大的提升。其中的一个难点在于怎么建立这么一个匹配关系表。其实除了我们目前这种推导和建立匹配关系的方法。我们还有一种和有限状态机相关的方法来解决这个问题。在后续的文章里会对这一块做一个进一步的补充。

 

参考资料

Algorithms

Introduction to algorithms