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 查询内容，然后一路后推即可。我当时的做法是自己准备一些笔纸，然后单步执行即可完成。

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

Github:https://github.com/yuikns/simple-kmp

效果如下：

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 !