摘 要 介绍了KMP算法并与朴素查找算法进行了比较,提出了前缀函数的概念,并利用改进的前缀函数改进KMP算法,最后结合KMP的改进算法给出了多次匹配的算法。
关键词 串匹配,前缀函数,KMP算法
1 KMP算法
最简单的朴素串匹配算法(BF算法)是从主串的 论文检测天使-免费论文检测软件http://www.jiancetianshi.com第一个字符和模式串的 论文检测天使-免费论文检测软件http://www.jiancetianshi.com
第一个字符进行比较,若相等则继续逐个比较后续字符,否则从主串的第二个字符起再重新和模式串的 论文检测天使-免费论文检测软件http://www.jiancetianshi.com
第一个字符进行比较。依次类推,直至模式串和主串中的一个子串相等,此时称为匹配成功,否则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移一个字符,若主串中存在和模式串只有部分匹配的多个子串,匹配指针将多次回溯,而回溯次数越多算法的效率越低,它的时间复杂度一般情况下为O((n-m+1)m) (注:n和m分别为主串和模式串的长度),最坏的情况下为O(m*n),最好的情况下为O(m+n)。KMP模式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是:当一趟匹配过程中出现失配时,不需回溯主串,而是充分利用已经得到的部分匹配所隐含的若干个字符,过滤掉那些多余的比较,将模式串向右“滑动”尽可能远的一段距离后,继续进行比较,从而提高模式匹配的效率,该算法的时间复杂度为O(m+n)。 那么如何确定哪些是多余的比较? 在KMP算法中通过引入前缀函数f(x)来确定每次匹配不需要比较的字符,保证了匹配始终向前进行,无须回溯。假设主串为s1s2,sn.,模式串为t1t2,tm.,其中 m≦n,从si+1开始的子串遇到一个不完全的匹配,使得: (1.1) 如果我们能确定一个最小的整数 ,使得: (1.2) 其中 ,所以确定i' 等价于确定k,这里的k值就是我们要求的前缀函数f(x)。由式1.1和1.2中K值与主串s无关,只与给定的模式串t中与主串匹配的q有关,即k=f(q),f(q)=max{i|0 i q且t[1..i]是t[1..q]的后缀} (1.3) 确定KMP前缀函数的算法如下 :#define MAXSIZE 100Typedef unsigned char string[MAXSIZE+1];//0号单元用来存放串的长度void f(sstring t, int *array){ m=t[0];//m为当前模式串的长度 array=(int *)malloc((m+1)*sizeof(int));//0号元不用 array[1]=0;k=0; for(q=2;q<=m;q++) {while(k>0&&t[k+1]!=t[q])k=array[k]; if(t[k+1]==t[q])k=k+1; array[q]=k; }} 关于KMP算法的前缀函数f(x)的示例见表1。
I | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Ti | a | b | a | a | b | c | a | c |
f(i) | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 0 |
朴素算法 | KMP算法 | |
时间复杂度 | O((n-m+1)m) | O(m+n) |
向前移动字符个数 | 1 | q-f(q) |
回溯次数 | q-1 | 无 |
[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr />
I | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Ti | a | b | a | a | b | c | a | c |
ff(i) | 0 | 0 | 1 | 0 | 2 | 0 | 1 | 0 |
3 利用改进算法实现多次模式匹配
在实际应用中,模式串与主串一般要进行多次匹配,以便找到在主串含有多少个这样的子串,典型的应用就是在数据库中的查找。例如输入某人的姓名,然后在姓名这一主串内查找有多少个这样的子串。下面结合前缀函数ff(x)的求解算法给出多次模式匹配的算法:void match(string s,string t, int a[]){ n=s[0];//主串的长度 m=t.[0];//模式串的长度 ff(t,f)//求出模式串中各个字符的前缀函数ff(x) d=0;//该变量用来统计与模式串匹配成功的子串的个数 q=0//该变量表示模式串中与主串匹配成功的字符的个数for(i=1;i<=n;i++) { while(q>0&&t[q+1]!=s[i]) q=f[q]; if(t[q+1]==s[i]) q=q+1; if(q==m) {d=d+1; a[d]=i-m+1;} }}4 结 语
本文给出的算法较朴素匹配算法在效率上有了较大的提高,尤其是对重复字符出现较少的数据段进行模式匹配可取得较高的查找效率。应用于大型数据库的数据查询,会更加有效地缩短查找时间。参考文献
[1]严蔚敏,吴伟民.数据结构[M].清华大学出版社, 2001[2]傅清祥,王晓东.算法与数据结构[M].电子工业出版社,1998[3]D.Wood,DataStructures,AlgorithmsAndPerfomance,Reading,MA:AddisonWesley,1993[4]onnetGH.HandbookofAlgorithmsAndDataStructure[M].Addison-WesleyPublishingCompany,1999
[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr />
相关文章:
计算机辅助历史教学及CAI课件的开发应用04-26
嵌入式家庭网关中SPI接口的软件模拟04-26
多媒体技术在新装备教学中的应用04-26
一种用VHDL设计嵌入式Web Server的方案04-26
细胞移植修复脊髓损伤的进展04-26
一种单片机综合实验系统的设计04-26
虚拟现实技术与VRML04-26