KMP算法简介及简单Java实现

继续复习算法+数据结构。今天简单写写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

如果pk+1 == pj+1,则f(j+1) = f(j) + 1
如果pk+1 != pj+1,则需要在 p0 p1 … pk-1 pk寻找子串 p0 p1 … ph-1 ph使得

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

如果ph+1 == pj+1,则可知f(j+1) = f(k)+1 = f(f(j)) +1;
如果ph+1 == pj+1,则需要在p0 p1 … ph-1 ph中寻找更小的h,把pj+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;
	}

One thought on “KMP算法简介及简单Java实现”

Leave a Reply

Your email address will not be published.