KMP算法(Knuth-Morris-Pratt)

KMP是一种优秀的字符串匹配算法，之前看了好多文章都没弄明白，现在说下自己的理解。

首先我们最普通的字符串匹配，比如在某个字符串中寻找子串，那么一个一个移动，逐个比较。 显然效率会比较低下。 下面说下KMP的做法。

部分匹配表(The Partial Match Table)

KMP算法最关键的就是这个表了。刚开始确实很难搞明白，下面先贴出这个表。然后再解释这个表的数据。

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 |

char就是我们的匹配串。 index 序号 value 待会儿解释~ :P

这里还需要引入2个概念，字符串前缀(Proper prefix)，字符串后缀(Proper suffix)

比如，字符串"hello"，那么

Proper prefix

"h" "he" "hel" "hell"

Proper suffix

"o" "lo" "llo" "ello"

很简单，不包含首尾字符的所有子串。

最长的字符串前缀和字符串后缀相匹配的长度(The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.)。

这个名字有点长。下面来解释下。我们看下上面表格的第3个格子，对应的字符串为"aba"，那么

2个Proper prefix(“a”，”ab”)

2个Proper suffix(“a”，”ba”)

那么这2组子串相互匹配上的，最大的长度就是 “a”的长度，那么对应的 value的值 =1

以此类推，第4个格子，对应的字符串为"abab"，那么

3个Proper prefix(“a”，”ab”，”aba”)

3个Proper suffix(“b”，”ab”，”bab”)

那么这2组子串相互匹配上的，最大的长度就是 “ab”的长度，那么对应的 value的值 =2

其余的可以以此类推…

部分匹配表的使用(How to use the Partial Match Table)

得到这个表之后，我们可以怎么使用呢？最开始我们提到了暴力匹配法就是逐个匹配，实际上我们可以用这个表格来跳过一些不必要的匹配，提高效率。那么跳过几个字符呢。假设当前匹配了n个字符，那么可以跳过n - table[n - 1] 个字符。看例子。

假设我们现在用匹配串"abababca"和主串"bacbababaabcbab"作匹配. 把上面的表格也搬过来，方便查看。

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 |

第一次匹配的时候：

bacbababaabcbab
 |
 abababca

这里的最长匹配上的子串大小为1 (也就是 a)，查表可得，table[n - 1] (此时n = 1，table[ 0 ])为0，那么不跳过任何字符。继续匹配：

bacbababaabcbab
    |||||
    abababca

这里的最长匹配上的子串大小为5，查表可得，table[n - 1](此时n = 5，table[ 4 ])为3 代入上面的公式 n - table[n - 1](5 - 3)，那么跳过2个字符：

bacbababaabcbab
    xx|||
      abababca

这里的最长匹配上的子串大小为3，查表可得，table[n - 1](此时n = 3，table[ 2 ])为1 代入上面的公式 n - table[n - 1](3 - 1)，那么跳过2个字符：

bacbababaabcbab
      xx|
        abababca

ok，这里的匹配串超出主串的长度了，都没匹配到，因此，结束。

原理简述

KMP 主要通过预先计算的部分匹配表来加速匹配过程的移动，可以跳过一些字符。 那么具体的部分匹配表怎么计算呢，代码如何实现，再来看下，代码很简短但是也比较难理解。

Code

vector<int> KMP(string s){
    vector<int> next(s.size());
    next[0] = 0;// 部分匹配表格 也就是上面的 value那一行，第一个字符最大前后缀长度是0
    int j = 0;
    for (int i = 1; i < s.size(); i++)//从第2个字符开始计算
    {
        while (j >0 && s[i]!= s[j])//循环 很关键，很难理解 下面解释
            j = next[j - 1];
        if (s[i] == s[j])
            ++j;
        next[i] = j;
    }
    return next;
}

重点说下 while循环做的事情：

1.已知前面计算最大前后缀长度为j，

2.此时比较s[j]和s[i]，如表1

3.如果相等，那么跳出while循环；

4.那么不等的情况？？？ 当s[i]和s[j]不等时，其实s[i-j]...s[i-1]和s[0]...s[j-1]是相同的。这个时候我们需要找一个s[0]打头、s[Newj - 1]结尾的子串，看看它的下一项s[Newj]是否和s[i]匹配。为什么是s[0]打头？求next[j]，就是求最大相同子串，所以是s[0]打头，都快忘了为什么出发了:P

那么Newj(更新后的j，避免混乱取个新的名字)值是什么，怎么来确定？看表2

表1

s[0] ... | s[i-j] ... s[i-1] | s[i] ...
                              =
         | s[0]   ... s[j-1] | s[j]
         | ..这一段是相同的..|

表2

s[0] ... | s[i-j] ... s[i-1] | s[i] ...
                               !=
         | s[0]   ... s[j-1] | s[j]
		 
         |  s[0]...s[Newj-1] | s[Newj]

看表2的s[0]...s[Newj-1],其实是s[0]...s[j-1]的后缀部分，同时也是整个s串的前缀部分。 也就是说s[0]...s[Newj-1]是s[0]...s[j-1]的最大相同前后缀，那么长度就是next[j-1]

最终得出很关键的一步 Newj=next[j-1] 对应代码里的while循环不相等情况下j = next[j - 1];，然后就是重复 2，3 步骤了

参考

jakeboxer 我见过的，写的最详细，简单的，看不懂我写的可以看这个。^_^

http://www.cnblogs.com/c-cloud/p/3224788.html 写的也很详细，图画的很清楚

• ← Previous Post
• Next Post →