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