Month: May 2009

继续复习算法+数据结构。今天简单写写KMP算法，不是那个KMPLAYER。。。同时这个话题也有很优秀的博文介绍，如Matrix67，我这里只是做些简单的小结。
KMP算法用于字符串的模式匹配，也就是查找某个字符串里是否存在某个子串，并返回位置，也就是Java/C++里的String.indexOf()方法。  字符串匹配最朴素的算法就是一个一个去比较，出错了就回溯到下一个起点继续比较。这样的复杂度有O(mn)，即原字符串×匹配串。而KMP算法能把时间复杂度降到O(m+n)。KMP这个缩写来自于Knuth，Morris和Pratt，瞬间想到了AVL树。
前面提到，朴素的匹配算法在出错后需要回溯到原来起点。但KMP不需要回溯到起点，直接从出错的位置继续进行比较，从而达到了O(n)。之所以不需要回溯，KMP的秘诀在于其用匹配串(Pattern)计算出来的一个数组F。每当进行字符串的比较卡壳在匹配串的第j个位置时(即Target[i] != Pattern[j])，查阅这个数组F，就可以知道下一次比较时j的值。举个例子：

• Source串(Target)：            a b a b a b a b a c b
• 匹配串(Pattern)：                a b a b a c b
• 根据Pattern得出的数组F: 0 0 1 2 3 0 0 (P怎么计算的后面会讲)

一一比较到第五个时前面的字符串都相等，到第六个时，由于Target[5] != Pattern[5]，所以需要知道下一次比较时，新的j值。j值越大，省略的比较越多。对于朴素的匹配算法，一旦卡壳在位置j，则下一次直接把j置0，即从第一个开始比较，并且回到这次比较的起点。而KMP则是得到新的j值（新的j值显然小于当前j值），并且不回到比较的起点，而是从这个地方继续比较下去，不吃回头草。
回到刚才的例子：

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a b a c b
Pattern: a b a b a c b
F:       0 0 1 2 3 0 0
j:       0 1 2 3 4 5 6

在j==5的地方，比较卡壳了，因为这时Target[5] != Pattern[5]，于是我们查找这时的F[j-1]==3，把j退回到3，继续比较。

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a b a c b
Pattern:     a b a b a c b
F:           0 0 1 2 3 0 0
j:           0 1 2 3 4 5 6

这个时候发现Target[i] == Patern[j]，于是继续前进

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a b a c b
Pattern:     a b a b a c b
F:           0 0 1 2 3 0 0
j:           0 1 2 3 4 5 6

到i=7, j=5时，比较又卡壳了。故伎重演，设j=F[j-1](如果依然Target[i] != Pattern[j]，则j=F[j-1]直到j=0。 如果这时候仍然 Target[i] !=Pattern[j]，就需要跳过Target[i]了)

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a b a c b
Pattern:         a b a b a c b
F:               0 0 1 2 3 0 0
j:               0 1 2 3 4 5 6

剩下就一路比较到结束。
如果把目标字符串（Target）改成abababadcb：

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a d a c b
Pattern:         a b a b a c b
F:               0 0 1 2 3 0 0
j:               0 1 2 3 4 5 6

Target[i] != Pattern[j], 则j = F[j-1] = 1

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a d a c b
Pattern:             a b a b a c b
F:                   0 0 1 2 3 0 0
j:                   0 1 2 3 4 5 6

仍然Target[i] != Pattern[j]，则j = F[j-1] = 0

i:       0 1 2 3 4 5 6 7 8 9 .
Target:  a b a b a b a d a c b
Pattern:               a b a b a c b
F:                     0 0 1 2 3 0 0
j:                     0 1 2 3 4 5 6

仍然Target[i] != Pattern[j]，且j==0，则跳过Target[i]，从Target的下一个字符开始比较。

以上介绍了KMP算法是如何使用神奇的P数组，在O(n)内完成字符串的搜索。下面的内容自然就是如何计算这个P数组，而且也还是在O(n)时间内。不过可能有些绕弯和复杂。
事实上，计算P数组本身只和模式字符串（Pattern）相关，而与目标（Target）字符串无关。因此我们只关注Pattern：ababacb。P数组的正式名称为失效函数(Failure Function)，f(j)的定义为，当模式字符串中第j+1个字符(Pattern[j])与目标字符串失配(mismatch)时，模式Pattern中应该由哪个字符（新的j)与刚才失配的字符对齐继续进行比较。对于我们刚才的使用的P数组而言，f(j) = F[j-1]。
f(j)实际上就是要寻找最大k(k<j)使得：

 p0 p1 ... pk-1 pk = pj-k pj-k+1 ... pj-1 pj

似乎看到了模式匹配的影子？的确，这个查找最大k的过程，实质上仍然是一个模式匹配的过程，只是目标和模式现在是同一个串的一部分。
我们使用递推的方式计算数组F（类似DP，但并不满足最优子问题）。设f(j)=F[j-1] = k，则

 p0 p1 ... pk-1 pk = pj-k pj-k+1 ... pj-1 pj

如果p_k+1 == p_j+1，则f(j+1) = f(j) + 1
如果p_k+1 != p_j+1，则需要在 p₀ p₁ … p_k-1 p_k寻找子串 p₀ p₁ … p_h-1 p_h使得

 p0 p1 ... ph-1 ph = pk-h pk-h+1 ... pk-1 pk = pj-h pj-h+1 ... pj-1 pj

如果p_h+1 == p_j+1，则可知f(j+1) = f(k)+1 = f(f(j)) +1；
如果p_h+1 == p_j+1，则需要在p₀ p₁ … p_h-1 p_h中寻找更小的h，把p_j+1给匹配进来。如果死活找不到这个h，则f(j+1)=0，即把j归0位。
继续Pattern=ababacb的例子：

a b a b a c b
0 0 1 ? ? ? ?
0 1 2 3 4 5 6

对于j=3，有f(3) = f(2) + 1 = 2

Pattern: a b a b a c b
F:       0 0 1 2 3 ? ?
j:       0 1 2 3 4 5 6

当j=5时，F[4] == 3，Pattern[5] != Pattern[3]，

Pattern: a b a b a c b
F:       0 0 1 2 3 ? ?
j:       0 1 2 3 4 5 6
             a b a b

那就试试f(2)=F[2-1]=1，发现Pattern[5] != Pattern[1]

Pattern: a b a b a c b
F:       0 0 1 2 3 ? ?
j:       0 1 2 3 4 5 6
                 a b a b

因此f(6) = F[5] = 0。
由于P只需要根据Pattern生成一次，所以KMP特别适用于多个Target字符串，单个Pattern串的情况。

下面给出算法的Java实现。我自己写的，可能还有些错误。遗憾的是Java里String.indexOf()方法的实现仍然是用朴素的字符串匹配方法。

	public static int indexOf(String target, String pattern){
		if(pattern.length() == 0){
			return 0;
		}
		int[] fail = getFail(pattern);
		int i=0,j=0;
		while(i < target.length()){
			if(target.charAt(i) == pattern.charAt(j)){
				i++;j++;
			}else if(j == 0){
				i++;
			}else{
				//往回查找j的位置
				j = fail[j-1];
			}
		}
		if(j < pattern.length()){
			return -1;
		}else{
			return i - pattern.length();
		}
	}
	//生成失效函数
	private static int[] getFail(String pattern){
		int[] fail = new int[pattern.length()];
		for(int j=1;j < pattern.length();j++){
			int k = fail[j-1];
			while(pattern.charAt(k) != pattern.charAt(j) && k > 0){
				k = fail[k];
			}
			if(pattern.charAt(k) == pattern.charAt(j)){
				fail[j] = k + 1;
			}else{
				fail[j] = 0;
			}
		}
		return fail;
	}