几种字符串匹配算法的分析和比较欧嵬,吴纯青(国防科技大学计算机学院,长沙410073)摘要:字符串匹配技术在许多领域里被广泛应用。分析了BF、KMP、BM算法以及一些重要的改进算法,并对其性能进行了测试,为不同的应用领域采用适当的算法提供了思路。关键词:模式匹配;串匹配;字符串检索;算法中图分类号:TP301文献标识码:A文章编号:1002-2279(2007)04-0059-03AnalysisandComparisonofSeveralStringMatchingAlgorithmsOUWei,WUChun-qingAbstract:Thetechnologyofstringmatchingisappliedabroadinmanyfields.ThispaperanalyzesBrute-Force,KMP,Boyer-Moorealgorithmsandthemostimportantimprovementstothesealgorithms,teststheperformancesofthesealgorithms.Itprovidescluesfordifferentfieldsmakinguseofappropriatearithmetic.Keywords:Patternmatching;Stringmatching;Stringsearching;Algorithm当时文本的起始比较位置,否则匹配不成功。该算法简单,但效率较低,在最坏情况下要进行m3(n-m+1)次比较,时间复杂度为O(m3n)。2.2KMP算法这是一种改进的模式匹配算法,其改进在于:每当一次匹配过程中出现字符不等时,不需回溯目标串,而是由已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离后,继续进行比较。以下是使用KMP算法的S串和T串的匹配过程。第一次匹配S:ABABCABCACBAB==≠T:ABCAC第二次匹配S:ABABCABCACBAB====≠T:ABCAC第三次匹配S:ABABCABCACBAB=====T:ABCAC当第一次匹配中目标串中第3个字符(位置以下用i标识)和模式串中第3个字符(位置以下用j标识)不相等时,i不变,模式串向右“滑动”,即从模式串第j个字符之前查找一个字符代替第j个字符和目标串的第i个字符继续比较。在第二次匹配中就是用第1个字符代替第j个字符与目标串的第i1引言模式匹配[1]是指在文本Text=tttt中检索123npm(模式)的所有出现,该技术在很子串Pat=p1p2多领域中广泛应用,如情报检索、文本编辑、入侵检测等等。模式匹配从方式上可分为精确匹配、模糊匹配、并行匹配等。著名的匹配算法有BF[2、4]算法、KMP[2-4]算法、BM[2、4]算法及一些改进算法[5-6]。2相关算法分析模式匹配主要有BF算法、BM算法及其改进算法,尤其是BM算法,在实际应用中非常著名,在此我们将对这几种算法做简单分析,分析前,我们做如下假定:文本:text[0..n-1],n为文本长度模式:pat[0..m-1],m为模式长度2.1BF算法BF(BruteForce)算法又称蛮力匹配算法[1],这是一种效率很低的算法,其算法主要思想是模式的第一个字符与文本的第一个字符进行比较,如果相同,就继续比较后面的字符,否则,文本的起始位置加1,即模式右移一个位置,再进行比较。如果模式与文本中一段连续字符串都相同,则匹配成功,作者简介:欧嵬(1978-),男,湖南长沙人,硕士研究生,主研方向:计算机网络与信息安全。收稿日期:2005-06-15个字符进行比较。改进后匹配算法的关键问题是:匹配过程中当字符不相等时,在模式串中找哪个字符代替第j个字符和目标串中的第i个字符比较,即模式串“向右滑动”多远?假设此时应是模式中的第k(k<j)个字符与目标串中的第i个字符比较,则模式中前k-符的比较却从右向左进行,即按p[m-1]、p[m-2]、p[0]的次序进行比较。在发现不匹配时,算法根据预先计算好的两个数组将模式向右移动尽可能远的距离。这两个数组称为shift和skip。假定失配发生时的情况如图1所示,此时已经匹配的部分为u,正文的b字符与模式的a字(1)‘t1t2tk-1=Si-k+1Si-k+2Si-1’正文text:模式pattern:而匹配过程中已经得到的“部分匹配”结果是:图1失配时的情况shift函数通过对已经匹配部分的考查决定模式右移的长度。失配发生时,如果u在模式中再次出现且前缀不是a字符(例如,是c字符),则将模式串右移使得正文中的u与满足上述条件的最右边的u对齐。如图2所示。‘t1t2tj-k+1tj-k+2tj-1=Si-j+1Si-j+2Si-k+1(2)Si-k+2Si-1’由(1)和(2)推得下列等式:‘t1t2tk-1=tj-k+1ti-k+2tj-1’(3)若模式串中存在满足式(3)的两个子串,则在匹配过程中,主串中第i个字符与模式中第j个字符不等时,仅需将模式向右滑动至模式中第k个字符和主串中第i个字符对齐,此时模式中前k-1个字符的子串‘t1t2...tk-1’必定与主串中第i个...