[转载]Linux 内核中的 KMP 实现

PS:2014年考研计算机综合408科目,增加了对字符串匹配算法的要求,当然也包括KMP。我只是理解了基本的next函数以及KMP算法的思想,再一次当了理论党。今天整理微博收藏的时候看到这篇博文,转载以加深记忆。讲解KMP的两篇博文:matrix67的和chaowork.com的。在淘宝搜索技术博客的这篇博文中有讲解除了KMP外的BM(后缀匹配)算法,不过只写了(一)没找到(二)呢。。。

Linux 内核中使用到了字符串搜索,所以它也有 KMP 算法的实现,代码在 lib/ts_kmp.c 中。

Linux 内核中用到 KMP 算法的地方有三处:iptables string match 模块、iptables conntrack amanda 模块(不知道这个是用来干什么的)、以及 ematch qdisc。iptables string match 是通过字符串搜索来匹配一个包,然后进行相应的处理,比如用下面的命令可以阻止对domain.com服务器的HTTP请求:

iptables -I INPUT 1 -p tcp –dport 80 -m string –string “domain.com” –algo kmp -j DROP

至于 ematch qdisc,和它类似,可以通过字符串匹配到对应的包进行 QoS,比如这个例子

tc filter add dev eth0 parent 10:12 prio 10 protocol ip basic match ‘text(kmp foobar from 0 to 200)’ flowid 10:1

总之,在内核中实现 KMP 算法是有必要的。下面来看具体实现。

我们知道,KMP 算法中最核心的地方就是 prefix 的计算,也称为 next 数组,它用来表示当字符 pattern[i] 匹配失败后应该从 pattern[next[i]] 字符继续进行匹配,而不总是从头开始,因此它的时间复杂度是O(n)。

内核中实现比网上的很多代码都更容易理解,因为在匹配开始之前,它就先把 prefix 计算好了。计算 prefix 的函数是:

结合 KMP 实现的主函数来理解更一目了然:

内核中的 KMP 函数接口是封装过的,你不能直接调用它。如果你的内核模块中要使用它,可以参考 lib/textsearch.c 中给的例子:

 

 

 

[转载]Linux 内核中的 KMP 实现》上有1条评论

  1. 张瑞昌

    博主可以看看July的文章,虽然July的代码功底不敢恭维,但是分析绝对是目前看过最细致的

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注