KMP 字符串匹配

现在有一个长字符串，以及一个短的key，从长的字符串中如何快速的找出和key匹配的字符串偏移 — 或者是存在与否呢？

代码本身超级简单

inline static void next_point(const char *pat, int next[]) {
  int times = 0;
  int j = 0, k = -1;
  next[0] = -1;

  while (j < (int)strlen(pat)) {
    times++;

    if (k == -1 || pat[j] == pat[k]) {
      j++;
      k++;
      next[j] = pat[k] == pat[j] ? next[k] : k;  // rewrite last line
    } else
      k = next[k];
  }
}

inline static int nkmp(const char src[], const char key[], int len_of_src,
                       int len_of_key) {
  int next[len_of_key];
  int index;
  int iter;
  int pos;
  next_point(key, next);

  for (index = 0; index < len_of_src; index++) {
    pos = 0;
    iter = index;

    while (pos < len_of_key && iter < len_of_src) {
      if (src[iter] == key[pos]) {
        iter++;
        pos++;
      } else {
        if (pos == 0)
          iter++;
        else
          pos = next[pos - 1] + 1;
      }
    }

    if (pos == len_of_key && (iter - index) == len_of_key) return index;

  }  // for end

  return -1;
}

inline static int kmp(const char *src, const char *key) {
  int len_of_src = strlen(src);
  int len_of_key = strlen(key);
  return nkmp(src, key, len_of_src, len_of_key);
}

其实就是先 encode 查询内容，然后一路后推即可。我当时的做法是自己准备一些笔纸，然后单步执行即可完成。

简单的几行代码可以从如下工程中获取：

效果如下：

yu:simple-kmp yu$ make
have a show :
LD_LIBRARY_PATH=. ./main
[found] offset: 6:
 [aaaaaaabbabbccdeggefegggabbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]
-> [abbabbccdeggefegggabbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]
-> [bbccdeggefegggabbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]

[found] offset: 14:
 [aaaaaaabbabbccdeggefegggabbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]
-> [abbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]
-> [aaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]

[found] offset: 29:
 [aaaaaaabbabbccdeggefegggabbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]
-> [abbaaaaaaaaabbba]
-> [aaaaaaaabbba]

[found] offset: -1:
 [aaaaaaabbabbccdeggefegggabbaaaadfbdcdfasdfasdfasdaadaaaaaabbaaaaaaaaabbba]
-> [aaaaaaaaabbba]
-> [aaaaabbba]

Complete !