算法-KMP算法

发表于 更新于 分类于 Disqus：
谈到字符串，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。

谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。

字符串匹配问题

一个字符串S，一个模式串P，如何查找P在S中的位置？

暴力匹配算法

思路如下：假设现在字符串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

  • 若当前字符匹配成功，即 S.charAt(i) == P.charAt(j) ，则i++, j++，继续匹配下一个字符串；
  • 若失配，即 S.charAt(i) != P.charAt(j)，则令 i = i - (j - 1), j= 0。相当于每次匹配失败时，i回溯，j被置为0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int forceMatch(String s, String p) {
  int sLen = s.length();
  int pLen = p.length();

  int i = 0;
  int j = 0;

  while(i < sLen && j < pLen) {
    if(s.charAt(i) == p.charAt(j)) {
      i++;
      j++;
    } else {
	  // 失配时，i回溯
      i = i - (j - 1);
      j = 0;
    }
  }

  if(j == pLen) {
    return i - j;
  } else {
    return -1;
  }
}

KMP算法

部分匹配表(PMT)

KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。

对于待匹配的字符串”abababca”来说，它的PMT表如下：

char a b a b a b c a
index 0 1 2 3 4 5 6 7
pmt-value 0 0 1 2 3 4 0 1

来看看这些PMT值是如何得出来的？

字符串前缀：如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。

字符串后缀：同样可以定义后缀A=SB， 其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

举例如下：

对于字符串”aba”来说，前缀集合：{“a”, “ab”}，后缀集合：{“ba”, “a”}，交集为：{“a”}，长度为1，即PMT值为1。

对于字符串”ababa”来说，前缀集合：{“a”, “ab”, “aba”, “abab”}，后缀集合：{“baba”, “aba”, “ba”, “a”}，交集为：{“aba”, “a”}，最大长度为3，即PMT值为1。

加速查找

假设要在主字符串”ababababca”中查找模式字符串”abababca”。

如果在 j 处字符不匹配，那么由于前边所说的模式字符串 PMT 的性质，主字符串中 i 指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的。这是因为主字符串在 i 位失配，也就意味着主字符串从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。而我们上面也解释了，模式字符串从 0 到 j−1 ，在这个例子中就是”ababab”，其前缀集合与后缀集合的交集的最长元素为”abab”， 长度为4。所以就可以断言，主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可。

简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

有了上面的思路，我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j 位 失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，所以为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next数组如下表所示。

char a b a b a b c a
index 0 1 2 3 4 5 6 7
pmt-value 0 0 1 2 3 4 0 1
next -1 0 0 1 2 3 4 0

next数组

求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。

具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。

next数组代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] getNext(String p) {
  int i = 0, j = -1;
  int len = p.length();
  int[] next = new int[len];
  next[0] = -1;

  while (i < len - 1) {
    if(j == -1 || p.charAt(i) == p.charAt(j)) {
      ++i;
      ++j;
      next[i] = j;
    } else {
      j = next[j];
    }
  }

  return next;
}

KMP代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int kmpMatch(String s, String p) {
  int sLen = s.length();
  int pLen = p.length();

  int i = 0;
  int j = 0;
  int[] next = getNext(p);
  while (i < sLen && j < pLen) {
    if(j == -1 || s.charAt(i) == p.charAt(j)) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  if(j == pLen) {
    return i - j;
  } else {
    return -1;
  }
}

参考

CSDN

知乎

阮一峰的网络日志

0%