KMP算法
对于KMP算法我分为两个部分说明，第一部分是算法部分，介绍KMP算法的算法思想；第二部分是实现部分，介绍一种厉害的实现代码以及代码注释。当然了由于本文主要介绍怎么实现故而先分析实现，对KMP理解不是很透彻的朋友可以先读算法介绍部分再来看代码。
(2). 算法实现：
首先提一句，当然在理解KMP的时候也很关键啦，就是说”KMP algorithm never re-compares a character in T that has matched a character in P”.其中T是目标串文本，P是模式串
下面给出大牛代码（来源不详）。
#define MAX_N 10010 char T[MAX_N], P[MAX_N]; //n为length of T , m 为length of P
int next[MAX_N],n,m; //compute array next[], next[i]表示P[0…i-1]中的
//the length of the longest proper prefix that matches a proper suffix
void kmpPreprocess()
{
int i=,j=-;
next[]=-;
while(i<m)//①为什么这一段代码可以顺利计算出next[]数组的值？？？
15 {
16 while(j>=0 && P[i]!=P[j])j=next[j];
17 i++, j++;
18 next[i]=j;
19 }
} void kmpSearch()
{
int i=,j=;
while(i<n)
{
while(j>= && T[i]!=P[j])j=next[j];
i++, j++;
if(j==m)
{
printf(“P is found at index %d in T\n”,i-j);
j=next[j];
}
}
}
下面就来分析一下为什么上述标红代码可以顺利计算出next[]数组的值。
首先，我们明确两点
- next[i]表示P[0…i-1]中的the length of the longest proper prefix that matches a proper suffix
- 每次循环开始的时候总有j=next[i]成立，也就是说明j是P[0…i-1]中的the length of the longest proper prefix that matches a proper suffix
其次，我们说明一下怎么去计算next[i+1]，这儿有两种情况。
- 当P[i]==p[j]时，那么next[i+1]=next[i]+1; 这个比较容易理解就不多说了。
- 如果不等，在这种情况下代码上面给出的操作是j=next[j]，什么意思呢，也就是说将j赋值为P[0..j-1] 中的the length of the longest proper prefix that matches a proper suffix，然后再来比较P[i]与p[j]的关系，递归。但是，为什么这么做是正确的呢？
这里我们来详细阐述一下，我们先来转换一下问题。
首先我们明确一点，那就是P[i]!=p[j]情况下next[i+1]的值比 P[i]==p[j]时候next[i+1]的值要小。又因为P[0…j-1]==P[i-j…i-1]，故而此时P[0…i]的the length of the longest proper prefix that matches a proper suffix等价于P[i-j…i] 的the length of the longest proper prefix that matches a proper suffix。于是我们要先找到P[i-j,i-1]中的the length of the longest proper prefix that matches a proper suffix，等于next[j]。
(1). 算法介绍：
这一部分我就不自己写了，因为我已经看到有人写的足够好的讲解了。
转自：http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
The Partial Match Table
The key to KMP, of course, is the partial match table. The main obstacle between me and understanding KMP was the fact that I didn’t quite fully grasp what the values in the partial match table really meant. I will now try to explain them in the simplest words possible.
Here’s the partial match table for the pattern “abababca”:
|
1 2 3 |
char: | a | b | a | b | a | b | c | a | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | |
If I have an eight-character pattern (let’s say “abababca” for the duration of this example), my partial match table will have eight cells. If I’m looking at the eighth and last cell in the table, I’m interested in the entire pattern (“abababca”). If I’m looking at the seventh cell in the table, I’m only interested in the first seven characters in the pattern (“abababc”); the eighth one (“a”) is irrelevant, and can go fall off a building or something. If I’m looking at the sixth cell of the in the table… you get the idea. Notice that I haven’t talked about what each cell means yet, but just what it’s referring to.
Now, in order to talk about the meaning, we need to know about proper prefixes and proper suffixes.
Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”.
Proper suffix: All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”.
With this in mind, I can now give the one-sentence meaning of the values in the partial match table:
The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.
Let’s examine what I mean by that. Say we’re looking in the third cell. As you’ll remember from above, this means we’re only interested in the first three characters (“aba”). In “aba”, there are two proper prefixes (“a” and “ab”) and two proper suffixes (“a” and “ba”). The proper prefix “ab” does not match either of the two proper suffixes. However, the proper prefix “a” matches the proper suffix “a”. Thus, the length of the longest proper prefix that matches a proper suffix, in this case, is 1.
Let’s try it for cell four. Here, we’re interested in the first four characters (“abab”). We have three proper prefixes (“a”, “ab”, and “aba”) and three proper suffixes (“b”, “ab”, and “bab”). This time, “ab” is in both, and is two characters long, so cell four gets value 2.
Just because it’s an interesting example, let’s also try it for cell five, which concerns “ababa”. We have four proper prefixes (“a”, “ab”, “aba”, and “abab”) and four proper suffixes (“a”, “ba”, “aba”, and “baba”). Now, we have two matches: “a” and “aba” are both proper prefixes and proper suffixes. Since “aba” is longer than “a”, it wins, and cell five gets value 3.
Let’s skip ahead to cell seven (the second-to-last cell), which is concerned with the pattern “abababc”. Even without enumerating all the proper prefixes and suffixes, it should be obvious that there aren’t going to be any matches; all the suffixes will end with the letter “c”, and none of the prefixes will. Since there are no matches, cell seven gets 0.
Finally, let’s look at cell eight, which is concerned with the entire pattern (“abababca”). Since they both start and end with “a”, we know the value will be at least 1. However, that’s where it ends; at lengths two and up, all the suffixes contain a c, while only the last prefix (“abababc”) does. This seven-character prefix does not match the seven-character suffix (“bababca”), so cell eight gets 1.
How to use the Partial Match Table
We can use the values in the partial match table to skip ahead (rather than redoing unnecessary old comparisons) when we find partial matches. The formula works like this:
If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters.
Let’s say we’re matching the pattern “abababca” against the text “bacbababaabcbab”. Here’s our partial match table again for easy reference:
|
1 2 3 |
char: | a | b | a | b | a | b | c | a | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | |
The first time we get a partial match is here:
|
1 2 3 |
bacbababaabcbab | abababca |
This is a partial_match_length of 1. The value at table[partial_match_length - 1] (or table[0]) is 0, so we don’t get to skip ahead any. The next partial match we get is here:
|
1 2 3 |
bacbababaabcbab ||||| abababca |
This is a partial_match_length of 5. The value at table[partial_match_length - 1] (or table[4]) is 3. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 5 - table[4] or 5 - 3 or 2) characters:
|
1 2 3 4 5 |
// x denotes a skip bacbababaabcbab xx||| abababca |
This is a partial_match_length of 3. The value at table[partial_match_length - 1] (or table[2]) is 1. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 3 - table[2] or 3 - 1 or 2) characters:
|
1 2 3 4 5 |
// x denotes a skip bacbababaabcbab xx| abababca |
At this point, our pattern is longer than the remaining characters in the text, so we know there’s no match.
Conclusion
So there you have it. Like I promised before, it’s no exhaustive explanation or formal proof of KMP; it’s a walk through my brain, with the parts I found confusing spelled out in extreme detail. If you have any questions or notice something I messed up, please leave a comment; maybe we’ll all learn something.