最近看到了KMP算法,第一次看这个也确实是头疼,上网查了一下发现确实又很多人都在说这个算法不好理解,于是我在自己搞懂之后,决定自己写一个KMP算法的教程(C语言),与大家分享一下。

引言和预备定义

首先介绍一种数据结构:串(string),指由零个或多个字符组成的有限序列,一般记为 s=’a1a2a3…an’,其中,s是串的名,n是串的长度。C语言中一般指字符串。

串中任意个连续的字符组成的子列称为该字符串的子串,包含子串的串相应的称为主串,称字符在序列中的序号为该字符在串中的位置。

我们称两个串是相等的,当且仅当这两个串的值相等,也就是说,这两个串长度相等且各个对应位置的字符也相等。

好了,有了这些定义,我们提出一个问题:“如果我们想要实现从一片字符串中,搜索到我们想要的内容(类似Ctrl+F一样的功能),对字符串进行精确匹配,那我们该怎么办呢?”

很显然,我们很快就能想到一个简单的算法:用一个指针指向主串的第一个字符,开始匹配,若不成功,则指针向前移位,重复操作直至成功。

代码如下:

int Match_String(char *s, char *t) {
  //在主串中匹配子串,并返回子串在主串中的位置
  int i = 0, j = 0;
  while(s[i] && t[j]) {
    if (s[i] == t[j])
      ++i, ++j;//比较下一个字符
    else
      i = i - j + 1, j = 0;//i退回到下一个字符,j归零
  }
  if (j == strlen(t))
    return i - j;//返回子串首字符对应的位置
  else
    return -1;//这里-1表示不匹配
}

接下来我们来考虑这个算法的时间复杂度,设主串的长度为n,子串的长度为m,则显然该算法的时间复杂度为O(m*n)。

仔细思考一下算法的过程,我们会发现,如果像下面这样,在一次匹配失败后,指针前进至主串的下一个字符,就像下面这样:

但是,仔细看一下会发现,由于子串是”abcda”,经过上一次的匹配,已经知道,接下来主串肯定是”bcd”的序列,肯定不可能与开头的”a”匹配,因此这样的匹配比较是多余的,要是能直接将子串移动到下面这张图这样,就减少了很多的时间,于是就有了接下来要讲的KMP算法。

算法主体

为了解决上面的问题,D.E.Knuth, J.H.Morris, V.R.Pratt三个人发现了这个算法,因此它被称作KMP算法。

回想刚才的情形,主串”abcabcadabca”,子串”abcad”开始和它匹配,前四个正常匹配,到了第五个开始发生了“失配”现象。

接下来,我们考虑子串这一下该向后移动多远,既然第五个不匹配了,那么我们就不考虑它,来看前四个字符,主串的第四个字符”a”与子串的第一个字符是一样的,于是我们可以把子串直接移动到主串的第四个字符处。

再看一个例子:主串”abcdefabcdefabce”,子串”abcdefabce”。第一次匹配,在第十个字符处发生“失配”,我们往前找发现第7-9个字符正好是子串的开头三个字符,于是将子串移动到主串第七个字符即可。

继续推广,便有:如果是主串中第i个字符和子串中第j个字符发生“失配”,我们只需要在主串中从第i-1位字符开始向前找,直到找到一个最长的序列,这个序列和子串开头的一段序列相等,那么我们把子串移动到该位置,不就好了吗?而且,主串在第i个字符之前的那一段完全和子串相同,我们只需要在子串上来寻找这段就可以了。当然了,如果我们怎么找也找不到这个序列,那就只能往后挪一个了。

于是,用公式来说明我们下一步该匹配谁的话,就是以下的next(j)函数了:

若next(j)表示”若子串中下标为j的字符发生‘失配’,则接下来用子串中下标为next(j)的字符来和主串中下标为i的字符进行比较”,则

next(j) =

  • k,k是一个最大的s,能从子串的下标为j-1的字符开始,向前找一个长为s的序列,它和子串开头s个字符相等。
  • 0,j = 1或者如果找不到上述的s;(这里就是向前迈进一步的意思)

有了next(j)函数之后,我们就可以用代码来实现KMP算法:

int KMP(char *s, char *t) {
  int i = 0, j = 0;
  while (s[i] && t[j]) {
    if (j == 0 || s[i] == t[j])
      ++i, ++j;//比较下一个字符
    else
      j = next(j);//比较第next(j)个字符
  }
  if (j == strlen(t))
    return i - j;//返回子串首字符对应的位置
  else
    return -1;//这里-1表示不匹配
}

那么,我们接下来的问题,就是探讨如何求得这个next(j)函数。

next(j)函数

既然next(j)实际上是一个数列,那么我们就用大家都会的方法——数列递推的方法来求解这个数列,设子串为t,主串为s。

  • 当j = 1时,只有t[0] = s[i-1] = t[j-1],那直接用t[1]去和s[i]比就行了,所以next(1) = 1。
  • 假设next(j) = n,即t[0]~t[n-1]和t[j-n]~t[j-1]相等,那么考虑next(j + 1)时的情形:
    1. 若t[n] = t[j],则显然我们找到了一个更长的匹配列:t[0]~t[n]和t[j-n]~t[j]相等,next(j + 1) = next(j) + 1;
    2. 若t[n] ≠ t[j],那么我们得从新考虑寻找子串开头与结尾的最长匹配列的问题,但是我们再一看,t[n] ≠ t[j],这不就是一个“失配”问题吗?好比从t[0]与t[j-n]开始配对,直到t[n-1]于t[j-1],但是在第n位上发生失配,这时该怎么办?按照我们上一节的讨论,应该寻求一个next(n)位来于t[j]位相配,这个时候,问题就变成递归性质的了,如果t[next(n)] = t[j],那么问题变成了第一条。如果t[next(n)] ≠ t[j],那么问题变成了第二条。

先别急着就写代码,我们来看看这个算法是否能再优化一下。因为每次比较,都要用到next(j)函数,如果我们每一次都这样用定义递归计算一次,那复杂度简直的不可想象的。所以,我们建立一个数组next[j]用来存放子串每一位对应的next(j)函数值,这样,如果设主串的长度是n,子串的长度是m,那么整个算法的时间复杂度为O(n + m)。

计算next[j]数组的函数如下:

void get_next(char *t, int *next) {
  int i = 1, j = 0;
  next[1] = 0;
  while(t[i]) {
    if (j == 0 || t[i - 1] == t[j - 1]) {//第一种情况
      ++i, ++j;
      next[i] = j;
    }
    else
      j = next[j];//第二种情况,直到相等为止才会进入上一个分支
  }
}

此时由于改成了用数组储存next函数,我们需要对KMP函数稍加修改一下:

int KMP(char *s, char *t, int *next) {
  int i = 0, j = 0;
  while (s[i] && t[j]) {
    if (j == 0 || s[i] == t[j])
      ++i, ++j;//比较下一个字符
    else
      j = next[j];//比较第next(j)个字符
  }
  if (j == strlen(t))
    return i - j;//返回子串首字符对应的位置
  else
    return -1;//这里-1表示不匹配
}

总结

第一次接触KMP算法的人,确实不容易想清楚这个问题,就我个人感觉,难点主要在两个地方:

  1. next(j)的求法。要点是把寻找匹配序列的时候,把整个问题也当做一个“失配问题”,自身既是主串也是子串。
  2. 代码实现时的下标问题。这个问题我在第一次自己写的时候也出现了很多问题,当然代码的实现自然有很多种,我这里就说我自己写的这种吧。一方面是实现next()的时候要想到用数组储存之前的值,否则你的递归会很麻烦。另一方面是实现next的比较过程,我用了t[i - 1] == t[j - 1],事实上比较确实可以从第一个开始,无需管第零个,但是这里涉及到存放next[j]数组的问题,所以考虑好下标后从这么写的。

所以说我们只要弄清楚next(j)函数,就把握了KMP算法的核心,对于这一块还是要加深理解。