现在有一个长字符串,以及一个短的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 !

Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

3 Comments

Vespa · January 1, 2014 at 14:23

Sogou Explorer Sogou Explorer Windows XP Windows XP

“看毛片”算法,当年第一次接触苦苦思考了一下午才明白。。。过了一阵子。。。又忘了。。

    yu · January 1, 2014 at 14:39

    Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 Windows 8.1 x64 Edition Windows 8.1 x64 Edition

    @Vespa 额..居然有这么雅致的一个别名..

    当时也想了好久,最后还是用单步走程序的方法搞定的.
    想通后其实发现也没啥的.就是编译一下key,然后比对,发现不对就跳转到某个特定的位置.

      Vespa · January 1, 2014 at 14:48

      Sogou Explorer Sogou Explorer Windows XP Windows XP

      @Yu Jing 嗯,以前最后也是看了一个数据结构书配套的演示光碟里面的动态演示才懂的。。

      这玩意儿,现在看书还比较好懂,但是程序让你在面试的时候当场写出来就比较胃疼了。。

Leave a Reply

Your email address will not be published.