字符串随机探测模式匹配算法.pdfVIP

第22卷 第6期 内蒙古民族大学学报(自然科学版) Vol_22 No．6 2007年12月 5oumal of Inner Mongolia University for Nationalities Dec．2oo7 字符串随机探测模式匹配算法 张春生 ，张晓英2，王国忠3 (1．内蒙古民族大学效学与计算机科学学院，内蒙古通辽 028043；2．内蒙古通辽市技工学校，内蒙古通辽 028046； 3．内蒙古通辽市第五中学，内蒙古通辽 028000) [摘 要】分析了目前字符串模式匹配的五种算法，总结了各种算法的时间复杂度和在不同场合下的不同表 现，并从经典算法出发，提出了一种随机探测模式匹配算法，同时评价了该算法的特点． [关键词】字符串；随机探测；模式匹配 [中图分类号】TP312 [文献标识码】A [文章编号]1671—0185(2007)06—0614—03 The Algorithm of String Random Probing Template Match ZHANG Chun—sheng ，ZHANG Xiao—yinE，WANG Guo—zhong3 (1．CoHege of Mathematics and Computer Science，Inner Mongdia Unirersity for Nationalities，Tongllao 028043，China； 2．The Technical School of Tongliao City of Inner Mongolia，Tongliao 028046； 3．The F．fth Middle School of Tongliao City of Inner Mongolia。Tongliao 028000) Abstract：This essay analyzes five algorithms of string template match of nowadays and summa— rizes their time complexity and different behaviors in different situations．Starting from classical algorithms，it presents the algorithm of random probing template match and evaluates the traits． Key words：String；Tandom probe；Template match 1 引言 字符串模式匹配问题在计算机程序中应用非常广泛，特别是在Internet上，更体现出其重要性．模式匹配算法的优劣， 直接影响到字符串的检索速度，关于字符串模式匹配问题的研究一直在进行，目前比较流行的有五种算法，本文首先分析 这五种算法的特点，分析其在不同的场合下不同表现，并从经典算法出发。提出了一种随机探测模式匹配算法，同时评价了 该算法的特点【l~3)． 2 目前算法的特点 字符串模式匹配目前存在朴素匹配算法、KMP匹配算法、改进KMP匹配算法、Boyer—Moore匹配算法、Rabin—KaW 匹配算法五种算法，这里首先谈谈这五种算法的特点，设主串长度为n，模式串长度为m． 2．1 朴素匹配算法 该算法从主串的第一个字符起与模式串的第一个字符比较，若相等。则继续逐个比较后续字符，否则 从主串第二个字符起再重新和模式串的字符比较，依次类推．该算法的特点是简单。容易理解，但时间复杂度太大，为O(m *n)． 2．2 KMP算法 KMP算法利用模式串部分匹配结果，在从左至右扫描过程中，主串的指针不回朔，这样使得该算法的时 闻复杂度很小，为O(m+12)，该算法效率很高，但需要事先计算next函数，且算法不易理解． 2．3 改进KMP匹配算法 改进KMP算法的实际上是KMP对朴素算法改进的继续，即充