KMP算法

来自计算思维百科
跳转至: 导航搜索
KMP算法1.png

我们经常在网上查找信息,例如在百度上键入“电影”就可以找到很多电影网站,这个过程就需要进行字符串匹配。

KMP算法是由D.E.Knuth、J.H.Morris、V.R.Pratt共同提出的一种字符串匹配算法。

基本概念

KMP算法的主要思想:每当一次匹配过程中出现字符不等时,不需要回退主串的指针,而是利用已经得到前面“部分匹配”的结果,将子串向右滑动若干个字符后,继续与主串中的当前字符进行比较,每次需要滑动的位移量记录在一个表中,这个位移量只有子串有关,从而使算法的效率有了很大的程度的提高。

应用范围

模式串的匹配算法在生活中很常见,在网络搜索工具中应用广泛。

应用案例

应用1- QQ搜索

腾讯QQ(简称“QQ”)是腾讯公司开发的一款基于Internet的即时通信(IM)软件。腾讯QQ支持在线聊天、视频通话、点对点断点续传文件、共享文件、网络硬盘、自定义面板、QQ邮箱等多种功能,并可与多种通讯终端相连。

它的功能已经非常强大。其中的搜索功能也很成熟了。

如在找群栏目,输入“刘亦菲”,就可以利用字符串的匹配算法,在数据库里找到相应的群聊,和志同道合的小伙伴进行交流啦。

KMP算法2.png
KMP算法3.png

应用2-馆藏搜索

案例:

下图为深圳大学图书馆的检索系统页面。

输入子串”计算机原理”,按任意字段关键字检索。

我们可以看到题名前三条分别为

“微机计算机原理与汇编语言程序设计”,

“微型计算机原理及应用教程”,

“微型计算机与接口技术”。

同样道理,在馆藏数据库的搜索中,如果无法搜索到完全匹配的词条名称,子串将滑动若干个字符,继续进行比较,直到搜索到含有子串全部关键字的题名。

KMP算法4.png

可以体现的计算思维

KMP字符串匹配算法是利用一个表记录了子串每次移动的位移,这个方法牺牲了空间换来了效率的提高,体现了计算思维的折中特点。