KMP 算法

KMP算法用于字符串的模式匹配,也就是查找某个字符串里是否存在某个子串,并返回位置,也就是Java/C++里的String.indexOf()方法。  字符串匹配最朴素的算法就是一个一个去比较,出错了就回溯到下一个起点继续比较。这样的复杂度有O(mn),即原字符串×匹配串。而KMP算法能把时间复杂度降到O(m+n)。KMP这个缩写来自于Knuth,Morris和Pratt,瞬间想到了AVL树。

前面提到,朴素的匹配算法在出错后需要回溯到原来起点。但KMP不需要回溯到起点,直接从出错的位置继续进行比较,从而达到了O(n)。之所以不需要回溯,KMP的秘诀在于其用匹配串(Pattern)计算出来的一个数组F。每当进行字符串的比较卡壳在匹配串的第j个位置时(即Target[i] != Pattern[j]),查阅这个数组F,就可以知道下一次比较时j的值。举个例子:

  • Source串(Target):              a b a b a b a b a c b
  • 匹配串(Pattern):                a b a b a c b
  • 根据Pattern得出的数组F:  0 0 0 1 2 3 0  (P怎么计算的后面会讲)  数字代表如果这次mismatch需要回到退几位

一一比较到第五个时前面的字符串都相等,到第六个时,由于Target[5] != Pattern[5],所以需要知道下一次比较时,新的j值。j值越大,省略的比较越多。对于朴素的匹配算法,一旦卡壳在位置j,则下一次直接把j置0,即从第一个开始比较,并且回到这次比较的起点。而KMP则是得到新的j值(新的j值显然小于当前j值),并且不回到比较的起点,而是从这个地方继续比较下去,不吃回头草。

由于P只需要根据Pattern生成一次,所以KMP特别适用于多个Target字符串,单个Pattern串的情况。

/** * Knuth-Morris-Pratt Algorithm for Pattern Matching */
public class KMPMatch {

  private String text;
  private String pattern;
  private int[] failure;
  private int matchPoint;

  ...
   /** * Finds the first occurrence of the pattern in the text. */
  public boolean match() {
    int j = 0;
    if (text.length() == 0) return false;

    for (int i = 0; i < text.length(); i++) {
     // p1: only execute when previous match is found and mismatch happend
      while (j > 0 && pattern.charAt(j) != text.charAt(i)) {
        j = failure[j - 1];
      }
      //p2: this p2 always execute before p1 
      if (pattern.charAt(j) == text.charAt(i)) { j++; }
      if (j == pattern.length()) {
        matchPoint = i - pattern.length() + 1;
        return true;
      }
    }
    return false;
  }
   /** * Computes the failure function using a boot-strapping process, * where the pattern is matched against itself. */
  private void computeFailure() {
    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) { 
        j = failure[j - 1];
      }
      if (pattern.charAt(j) == pattern.charAt(i)) { 
        j++; 
      }
      failure[i] = j;
    }
  }
  ...
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s