关于两个字符串的kmp比对算法

假设有字符串X和Y，满足len(X)>len(Y)，要比对这两个字符串。

我们知道，最朴实的方法，就是现将二者对齐，然后依次比对对应位置的字符。如果能匹配到Y最后位置，则匹配成功；如果匹配失败，则将Y右移一位，再从头进行匹配。

设字符串X为dababeabafdababcg；字符串Y为ababc。

这种比对方法如下所示：

起始时，二者对其，第一个字符不匹配

:|
:dababeabafdababcg
:ababc

右移一位，比对位置移动到Y起始位置

: |
:dababeabafdababcg
: ababc

连续成功4次，再次遇到不匹配

:     |
:dababeabafdababcg
: ababc

右移一位，比对位置移动到Y起始位置

:  |
:dababeabafdababcg
:  ababc
:

不断重复该过程，直到…………

:               |
:dababeabafdababcg
:           ababc

Y完整匹配到X，结束。

毫无疑问，这种方法太笨了。时间复杂度高达O(mn)。最大的问题是，进行了大量的重复比对工作。

kmp算法正是为了解决这一点而提出的。kmp算法的中心思想是，已经匹配的部分不需要再次去匹配，相反，应根据已匹配的部分进行多字节的挪动，加快匹配速度。

怎么做呢？kmp给出的答案是：

已经匹配的部分，可以说是已知的，而且是只取决于字符串Y的，对字符串Y的挪动可以直接挪动到下一个满足匹配的位置。

什么叫下一个满足匹配的位置？

假设字符串X和字符串Y已经匹配的部分为abcab，显然：

: abcab...  : abcab...   :
:  abcab... :   abcab... :

都是不匹配的，只有如下的

:abcab...
:   abcab...

才匹配。显然，新的匹配序列，是旧的匹配序列的一个真后缀，而且还是字符串Y的一个前缀；而旧的匹配序列也是字符串Y的前缀。

也就是说，根据已经匹配的部分，我们已经可以排除大量的位置了。kmp算法正是基于这一原理实现的。

规则1
如果当前比对位置两个字符相同，则比对位置右移1位
规则2
如果当前比对位置两个字符不同，则：

如果没有匹配到序列，则比对位置右移1位，字符串Y右移1位
如果已有匹配到序列，则移动字符串Y到下一个匹配位置

如下例，起始

:|
:dababeabafdababcg
:ababc

字符不匹配，比对位置和字符串Y都右移一位

: |
:dababeabafdababcg
: ababc

字符匹配，比对位置右移1位

:  |
:dababeabafdababcg
: ababc

连续成功匹配4次，再次遇到不匹配

:     |
:dababeabafdababcg
: ababc

字符不匹配，挪动字符串Y到下一个匹配位置

:     |
:dababeabafdababcg
:   ababc

仍旧不匹配，继续挪动字符串Y

:     |
:dababeabafdababcg
:     ababc

仍旧不匹配，已经没有匹配序列了，比对位置和字符串Y都右移一位

:      |
:dababeabafdababcg
:      ababc

字符匹配，比对位置右移1位

:       |
:dababeabafdababcg
:      ababc

连续成功匹配3次，再次遇到不匹配

:         |
:dababeabafdababcg
:      ababc

字符不匹配，挪动字符串Y到下一个匹配位置

:         |
:dababeabafdababcg
:        ababc

仍旧不匹配，继续挪动字符串Y

:         |
:dababeabafdababcg
:         ababc

字符不匹配，无匹配序列，比对位置和字符串Y都右移一位

:          |
:dababeabafdababcg
:          ababc

字符不匹配，无匹配序列，比对位置和字符串Y都右移一位

:           |
:dababeabafdababcg
:           ababc

字符匹配，比对位置右移1位

:            |
:dababeabafdababcg
:           ababc

连续成功匹配5次，到达字符串Y终点，匹配成功

:               |
:dababeabafdababcg
:           ababc

由此可见，kmp算法的比对位置没有倒车的情况，而且同一位置比对的次数也明显少于朴实算法，比对速率是相当快的。

kmp算法的关键，是根据已有匹配序列计算下一个匹配序列，而这一部分，是只需要字符串Y就可以实现的，因为下一匹配序列的计算和已有匹配序列之外的部分，无关。

事实上，根据已有匹配序列，完全可以得到多个满足要求的下一级匹配序列（即既是已有匹配序列的真后缀，又是字符串Y的前缀），但是毫无疑问，我们应该选择最长的那个。

kmp算法的关键，也就是对根据已有匹配序列计算下一个匹配序列这一个步骤的计算了，因为我们知道下一匹配序列必然是字符串Y的前缀，实际上只需要记录下一匹配序列的长度即可。这也就是所谓的next数组的真面目。（其他人介绍的next数组的值可能和我说的不同，但实际上都是对下一匹配长度进行数学变换的结果）

那么关于next数组的计算，自然也有多种方法，比如很朴实的方法，我就不多说了。事实上，有个很好的方法可以轻松的计算出next数组。这个方法和kmp本身比对的过程有些类似，同时也和后缀树构树的ukkonen算法有异曲同工之妙。

go代码如下：

// 成员n[i]表示既是s[:i]真后缀又是s前缀的最长序列的长度。
// 真后缀指非自身的非空后缀。如不存在，则置该成员值为0。
func next(s string) []int {
   n := make([]int, l)
   // 从n[2]开始算起
   for i, j := 2, 0; i < l; {
       // 已知前面的字符全部匹配
       if s[i-1] == s[j] {
           j++
           n[i] = j
           i++
           continue
       }
       if j == 0 {
           // 申请的n会全部初始化为零
           i++
           continue
       }
       // 类似后缀指针的功用
       j = n[j]
   }
   return n
}

我们每一次循环的时候，只进行了一个字符的比对！这是因为之前的比对已经保证前面的部分是匹配的。那么如果这一次比对成功，只需要延长下一次匹配的长度就行了；如果比对失败，我们也不需要从头开始去查找下一个匹配的起始位置，因为之前的匹配结果已经告诉了我们下一个匹配的位置。

结果是，kmp算法构造next数组和比对的过程，都很迅速！

kmp算法完整代码如下：

// kmp字符串搜索算法
func KMP(s, r string) int {
   l := len(r)
   // 成员n[i]表示既是s[:i]真后缀又是s前缀的最长序列的长度。
   // 真后缀指非自身的非空后缀。如不存在，则置该成员值为0。
   n := func(s string) []int {
       n := make([]int, l)
       // 从n[2]开始算起
       for i, j := 2, 0; i < l; {
           // 已知前面的字符全部匹配
           if s[i-1] == s[j] {
               j++
               n[i] = j
               i++
               continue
           }
           if j == 0 {
               // 申请的n会全部初始化为零
               i++
               continue
           }
           // 类似后缀指针的功用
           j = n[j]
       }
       return n
   }(r)
   // 进行搜索
   i, j := 0, 0
   for i+l < j+len(s) && j < l {
       if s[i] == r[j] {
           i, j = i+1, j+1
           continue
       }
       if j == 0 {
           i++
       } else {
           j = n[j]
       }
   }
   if j == l {
       return i - l
   }
   return -1
}

kmp算法是一个相当精巧，但是代码却非常简单的算法。相比之下，虽然速度可能逊色于BM算法，但是确实优美得多。

关于两个字符串的kmp比对算法