继续复习算法+数据结构。今天简单写写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 0){
k = fail[k];
}
if(pattern.charAt(k) == pattern.charAt(j)){
fail[j] = k + 1;
}else{
fail[j] = 0;
}
}
return fail;
}
OnlyMarshall 
KMP就复习的时候看了一下，现在都忘差不多了……
LikeLike