第３６卷　第１期２０１６年０１月
西安科技大学学报
ＪＯＵＲＮＡＬＯＦＸＩ’ＡＮＵＮＩＶＥＲＳＩＴＹＯＦＳＣＩＥＮＣＥＡＮＤＴＥＣＨＮＯＬＯＧＹ
Ｖｏｌ．３６　Ｎｏ １
Ｊａｎ ２０１６
    ＤＯＩ：１０．１３８００／ｊ．ｃｎｋｉ．ｘａｋｊｄｘｘｂ．２０１６．０１１９文章编号：１６７２－９３１５（２０１６）０１－０１１１－０５
字符串匹配算法Ｓｕｎｄａｙ的改进
朱宁洪
（西安科技大学计算机科学与技术学院，陕西西安７１００５４）
摘　要：字符串的模式匹配应用十分广泛，在信息的搜索查询等方面具有重要作用，研究串匹配
算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上，对当前
应用最广泛的Ｓｕｎｄａｙ算法提出了改进的算法Ｚｈｕｓｕｎｄａｙ．算法主要改进之处是：在字符串从右向
左匹配过程中，当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时，算法从
右向左搜索当前文本字符在模式串中出现的位置；到当前字符在模式串中的位置后继续再向
左匹配模式串字符一次，如果仍不匹配时，模式窗口比Ｓｕｎｄａｙ算法多向右移动一个字符。改进的
算法提高了模式匹配的执行效率，通过大量对比实验证明了该算法的有效性。最后得出结论：在
实际应用中，坏字符大量存在的情况下，改进算法的最优时间复杂度可达Ｏ（ｎ／ｍ），在同一时间复
杂度下，比Ｓｕｎｄａｙ算法效率提高２５～５０％．
关键词：Ｓｕｎｄａｙ算法；Ｚｈｕｓｕｎｄａｙ算法；模式匹配；坏字符
中图分类号：ＴＰ３９１  　文献标志码：Ａ
ＩｍｐｒｏｖｅｍｅｎｔｏｆＳｕｎｄａｙｐａｔｔｅｒｎｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍ
ＺＨＵＮｉｎｇ ｈｏｎｇ
（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｉ’ａｎ７１００５４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｓｔｒｉｎｇｐａｔｔｅｒｎｍａｔｃｈｉｎｇｉｓｗｉｄｅｌｙｕｓｅｄｉｎｉｎｆｏｒｍａｔｉｏｎｓｅａｒｃｈａｎｄｑｕｅｒｙ，ａｎｄｉｔｉｓｉｍｐｏｒｔａｎｔｔｏ
ｓｔｕｄｙｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｓｔｒｉｎｇｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｗｉｔｈｔｈｅｏｒｅｔｉｃａｌｖａｌｕｅａｎｄｐｒａｃｔｉｃａｌｓｉｇｎｉｆｉｃａｎｃｅ．Ｏｎ
ｔｈｅｂａｓｉｓｏｆｔｈｅａｎａｌｙｓｉｓｏｆｓｅｖｅｒａｌｃｌａｓｓｉｃａｌｐａｔｔｅｒｎｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｓ，ｔｈｅｐａｐｅｒｐｕｔｓｆｏｒｗａｒｄａ
ＺｈｕｓｕｎｄａｙａｌｇｏｒｉｔｈｍｗｈｉｃｈｉｓｉｍｐｒｏｖｅｄｆｒｏｍｔｈｅｍｏｓｔｗｉｄｅｌｙｕｓｅｄＳｕｎｄａｙａｌｇｏｒｉｔｈｍ．Ｔｈｅｉｍｐｒｏｖｅｄｐｏｓｉ
ｔｉｏｎｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｓ：ｉｎｔｈｅｍａｔｃｈｉｎｇｐｒｏｃｅｓｓｆｒｏｍｔｈｅｒｉｇｈｔｏｆｔｈｅｔｅｘｔｓｔｒｉｎｇｔｏｔｈｅｌｅｆｔ，ｗｈｅｎｔｈｅｃｈａｒ
ａｃｔｅｒｏｆｔｈｅｔｅｘｔｄｏｅｓｎｏｔｍａｔｃｈｔｈｅｃｈａｒａｃｔｅｒｏｆｔｈｅｐａｔｔｅｒｎｓｔｒｉｎｇ，ｉｔｉｓｎｏｔａｂａｄｃｈａｒａｃｔｅｒ，ｔｈｅａｌｇｏｒｉｔｈｍ
ｓｅａｒｃｈｅｓｔｈｅｐｏｓｉｔｉｏｎｏｆｔｈｅｃｕｒｒｅｎｔｔｅｘｔｃｈａｒａｃｔｅｒｆｒｏｍｔｈｅｒｉｇｈｔｔｏｔｈｅｌｅｆｔｉｎｔｈｅｐａｔｔｅｒｎｓｔｒｉｎｇ．Ａｆｔｅｒ
ｆｉｎｄｉｎｇｔｈｅｐｏｓｉｔｉｏｎ，ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｃｏｎｔｉｎｕｅｓｔｏｍａｔｃｈｔｈｅｔｗｏｃｈａｒａｃｔｅｒｓｉｎｔｈｅｌｅｆｔｆｏｒａｎｏｔｈｅｒ
ｔｉｍｅ．Ｉｆｔｈｅｒｅｉｓｎｏｍａｔｃｈ，ｔｈｅｐａｔｔｅｒｎｗｉｎｄｏｗｗｉｌｌｍｏｖｅｔｏｒｉｇｈｔｏｎｅｓｔｅｐｍｏｒｅｔｈａｎｔｈｅｍｏｖｅｍｅｎｔｏｆ
Ｓｕｎｄａｙａｌｇｏｒｉｔｈｍ．Ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｓｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｐａｔｔｅｒｎｍａｔｃｈｉｎｇ，ａｎｄｔｈｅｅｆｆｅｃ
ｔｉｖｅｎｅｓｓｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｐｒｏｖｅｄｂｙａｌｏｔｏｆｅｘｐｅｒｉｍｅｎｔｓ．Ｆｉｎａｌｌｙｔｈｅｐａｐｅｒｄｒａｗｓａｃｏｎｃｌｕ
ｓｉｏｎ：ｉｎｐｒａｃｔｉｃａｌａｐｐｌｉｃａｔｉｏｎｔｈｅｒｅａｒｅａｌａｒｇｅｎｕｍｂｅｒｏｆｔｈｅｂａｄｃｈａｒａｃｔｅｒｓ，ｔｈｅｏｐｔｉｍａｌｔｉｍｅｃｏｍｐｌｅｘｉｔｙ
ｏｆｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｓＯ（ｎ／ｍ），ａｎｄａｔｔｈｅｓａｍｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙ，ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｓｍｏｒｅ
ｅｆｆｉｃｉｅｎｔｔｈａｎｔｈｅＳｕｎｄａｙａｌｇｏｒｉｔｈｍｂｙ２５～５０％．
Ｋｅｙｗｏｒｄｓ：Ｓｕｎｄａｙａｌｇｏｒｉｔｈｍ；Ｚｈｕｓｕｎｄａｙａｌｇｏｒｉｔｈｍ；ｐａｔｔｅｒｎｍａｔｃｈｉｎｇ；ｂａｄｃｈａｒａｃｔｅｒ
收稿日期：２０１５－０７－２９  　责任编辑：高　佳
基金项目：国家自然基金（煤炭联合基金）（Ｕ１２６１１１４）
作者简介：朱宁洪（１９６９－），男，山东兖州人，讲师，Ｅ ｍａｉｌ：ｚｈｕｎｉｎｇｈｏｎｇ＠ｓｏｈｕ．ｃｏｍ
博看网 . All Rights Reserved.
０　引　言
字符串匹配问题是计算机科学中的最基本的问题，如何能在最短的时间内确定特征字符串在文本中是否
出现过具有重要的意义。在现实中，串匹配的应用十分广泛，主要领域包括：文档编辑、内容管理、计算机病毒检测、信息检索、符号操作、搜索引擎、
ＤＮＡ序列检测以及入侵攻击检测等等［
１］
。而且，串匹配是这些应用中的关键模块，优良的串匹配算法能大幅地提高应用系统整体的效
率［２］
。因此，研究字符串的模式匹配算法的效率具有重要的理论价值和实际意义［３］。
设文本串Ｔ＝Ｔ０…Ｔｎ－１
，ｎ为文本串Ｔ的长度；模式串Ｐ＝Ｐ０…Ｐｍ－１，ｍ为模式串的长度（ｎ ｍ）。在Ｔ中寻等于Ｐ的子串，如果在Ｔ中存在等于Ｐ的子串，则称匹配成功，函数值返回Ｐ第一次出现
在文本串Ｔ中时Ｐ的首字符的在Ｔ中的下标，否
则称为匹配失败，这个搜索过程就是模式匹配［
４］
。按照匹配遍历时被查的模式串个数划分，字符串匹配算法又可以分为２种：
单模式匹配和多模式匹配。单模式匹配算法遍历一次可以搜索一个字符串，多模式匹配算法能够在遍历一次的情况下，搜索出文本中模式串里多个模式串的所有出现位置。目前，国内外对于模式匹配算法已有不少的研究成果，比如典型的单模式算法有ＢＦ算法、
ＫＭＰ算法、ＢＭ算法、Ｓｕｎｄａｙ算法，多模式算法主要有ＡＣ算法、Ｗｕ＿Ｍａｎｄｅｒ算法［５］
。鉴于许多单
模式搜索算法能够扩展成多模式搜索算法，在此简要介绍４种经典单模式匹配算法。
１　几种经典的模式匹配算法
ＢＦ算法是效率最低的算法，又称蛮力匹配算
法［６］。在文本串中从左到右进行匹配。首先将Ｔ
［０］与Ｐ［０］进行比较，若相等，则逐个比较后续字符；否则，就将Ｔ［１］与Ｐ［０］进行比较，继续开始下一趟的比较，重复上述过程。算法特点是简单易
理解，但时间复杂度较大，为Ｏ（ｍ ｎ
）［７］。ＫＭＰ算法是由ＢＦ改进后不产生回溯的一种算法，每当匹配过程中出现字符串匹配不等时，不需回溯指针，而是利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离后，继续进行比较。模式串不一定向右移动一个字符的位置，右移也不是必须从模式串起点处重新试匹配，也就是模式串可以一次向右移动多个字符的位
置，右移后可以从模式串起点后的某处开始试匹配。理论上时间最优复杂度可达到Ｏ（ｍ＋ｎ）；空
间复杂度Ｏ（ｎ）［８］
。
ＢＭ算法在匹配过程中方向是由左向右，但是
在比较过程中方向是由右向左［
９］
，也就是把Ｐ同Ｔ进行比较时从右向左。当某趟匹配失败时，采用坏字符（在Ｔ串中存在而Ｐ串中没有的字符称为坏字符）规则和好后缀规则计算模式串右移的距离，并取两者最大值来决定模式串的右移量，移动尽可能远的距离，直到匹配成功或文本串匹配结束。匹配时从右至左进行。Ｂ
Ｍ算法的最坏时间复杂度为Ｏ（ｍ ｎ），但由于实际应用中这种情况极少出现，因此ＢＭ算法仍然得到广泛应用。特别是当发现不匹配的字符时可以使用好后缀和坏字
符进行跳转，降低无效的匹配次数［
１０］
。Ｓｕｎｄａｙ算法是最新的对ＢＭ算法进行了大幅改进的算法，
Ｓｕｎｄａｙ算法采用ＢＭ算法中的坏字符启发规则，和ＢＭ算法相比效率有了较大的提高，在实践中得到了广泛使用，具有新颖性和代表性。下面以在Ｔ串“
ａｂｃｏｅｆｃａｃｄｘｄｂｃｄ”中查模式串Ｐ“ｄｂｃｄ”的过程来介绍Ｓｕｎｄａｙ算法，算法的匹配过程如图１所示。
Ｔ串
ａｂｃｏｅｆｃａｃｄｘｄｂｃｄ匹配次数Ｓｕｎｄａｙ
算法模式串ｐ位置
×                          ｄｂｃｄｏｄ不匹配，ｏ不存在，且下一字符ｅ１＝ｐ［０］，Ｐ窗口向左移５．
×                              ｄｂｃｄｃｄ不匹配，ｐ中ｃ与Ｔ中ｃ对齐，右移１．
×              √√                              ｄｂｃｄａｂ不匹配，将Ｐ中右侧第２个ｄ与Ｔ当前ｄ对齐，Ｐ
窗口右移３．              ×                              ｄｂｃｄｂｄ不匹配，ｐ中右侧第１个ｂ与Ｔ当前ｂ对齐，Ｐ窗口右移２．
√√√√
ｄｂｃｄ匹配成功
１
２
fastjson字符串转数组３
４
５（成功）图１　Ｓｕｎｄａｙ算法执行情况
Ｆｉｇ．１　ＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＳｕｎｄａｙａｌｇｏｒｉｔｈｍ
Ｓｕｎｄａｙ算法过程叙述如下：开始时模式串Ｐ的左边与文本串Ｔ的左边对齐；模式匹配过程中进行Ｐ与Ｔ的比较时，
从右向左反向进行比较，反复比较匹配，直到到模式串或文本串比较完。比较过程中有２种情况１）和２）
１）在发现与Ｐ最右侧第一个字符对应位置的
２１１        　西安科技大学学报          　２０１６年　
博看网 . All Rights Reserved.
第１期朱宁洪：字符串匹配算法Ｓｕｎｄａｙ的改进
Ｔ字符不匹配时，又分２种情况Ａ和Ｂ：Ａ．当前字符是坏字符因此发生不匹配时，如果Ｔ当前字符右
面的字符依然不匹配模式串Ｐ的第一个字符ｐ［０］，模式窗口向右移动ｍ＋１（ｍ为Ｐ长度），如果当前的字符匹配，模式窗口则只向右移动ｍ（ｍ为Ｐ模式串的长度）继续下一轮匹配（此时情况与图１中的Ｓｕｎｄａｙ算法第一次匹配的情况相同）；Ｂ．如果不是坏字符，则在Ｐ中由右向左查Ｔ中当前字符，让模式窗口从右向左第一次出现该字符的地方与Ｔ中当前字符对齐，继续下一轮的匹配（此时情况最常见，与图１中的Ｓｕｎｄａｙ算法第２次和第４次匹配的情况相同）；
２）在发现与Ｐ最右侧第一个字符对应位置的Ｔ字符匹配时，Ｐ向左取第二个和Ｔ再向左取的第二个字符继续匹配，一直匹配到字符不同或匹配完ｐ串。也有２种情况Ｃ和Ｄ：Ｃ．如果未能匹配完，则Ｔ当前的不匹配字符ｄ与在模式串中从右侧第一次出现ｄ的位置对齐，继续下一轮的匹配；（此时情况与图１中的Ｓｕｎｄａｙ算法第３次匹配的情况相同）Ｄ．如果一直匹配，直到Ｐ所有字符匹配完，则返回Ｔ中与Ｐ［０］对应的开始位置作为匹配位置，算法结束（此时情况与图１中的Ｓｕｎｄａｙ算法第５次匹配的情况相同）。
Ｓｕｎｄａｙ算法在最坏情况下的计算复杂度为Ｏ（ｍ ｎ）。但是在实际使用中文本串的坏字符出现概率非常高，最好情况（在到Ｐ串以前遇到的字符都是坏字符）下的时间复杂度可达到Ｏ（ｎ／ｍ），所以在实践中应用广泛。Ｓｕｎｄａｙ算法是目前单模式匹配算法中比较成熟，且效率最高的一种。
２　Ｓｕｎｄａｙ算法的改进
下面是用Ｓｕｎｄａｙ算法和改进的算法（称之为Ｚｈｕｓｕｎｄａｙｓ算法）进行模式串匹配的一个例子，具体说明２个算法相同部分和不同
文本串Ｔ＝“ａｂｃｏｅｆｃａｃｄｘｄｂｃｄ”，模式串Ｐ＝“ｄｂｃｄ”．Ｓｕｎｄａｙ算法和Ｚｈｕｓｕｎｄａｙ算法在模式窗口中都由右向左匹配。Ｓｕｎｄａｙ算法匹配过程（如图１所示）上面已经叙述完毕，下面叙述Ｚｈｕｓｕａｎｄａｙ算法，其具体匹配过程如图２所示。
Ｚｈｕｓｕｎｄａｙ算法针对Ｓｕｎｄａｙ算法最常见的（１）Ｂ和（２）Ｃ情况进行了改进，其余部分和Ｓｕｎ ｄａｙ算法一样。改进之处在于
Ｔ串ａｂｃｏｅｆｃａｃｄｘｄｂｃｄ匹配次数
ｚｈｕｓｕ
ａｎｄａｙ
算法模
式串ｐ
位置
×
ｄｂｃｄ
ｏｄ不匹配，ｏ不存在，且下一字符ｅ１＝ｐ［０］，Ｐ窗口向
左移５．
×
ｄｂｃｄ
ｃｄ不匹配，Ｐ中右侧第１个ｃ与Ｔ中ｃ对齐，Ｐ窗口右
移１；同时，Ｐ串ｃ左侧ｂ与对应Ｔ串ｃ左侧字符ａ不
同，Ｐ窗口需再右移１．
×
ｄｂｃｄ
ｄｘ不匹配，ｘ不在Ｐ串，Ｔ下一字符ｄ＝＝ｐ［０］，Ｐ窗
口右移４．
√√√√
ｄｂｃｄ
匹配成功
１
２
３
４（成功）
图２　Ｚｈｕｓｕｎｄａｙ算法执行情况
Ｆｉｇ．２　ＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＺｈｕｓｕｎｄａｙａｌｇｏｒｉｔｈｍ
１）在Ｓｕｎｄａｙ算法最常见的（１）Ｂ情况（也就是不匹配，且不是坏字符，向前不能完全匹配，与图１中的Ｓｕｎｄａｙ算法第２次和第４次匹配的情况相同）下，只让Ｐ中当前字符与Ｔ对应的字符对齐，对齐是假定Ｔ当前字符左侧的字符与Ｐ当前字符左侧的字符相同（２个连续字符都相同一般情况下是不常见的），已经在Ｐ中从右向左查到了当前字符，但是，如果假定不成立，就可以多移动一个字符的位置，算法开销的成本就是多比较一个字符，这种情况和图２中Ｚｈｕｓｕｎｄａｙ算法第２次匹配一样。如果相同，就和原来移动步数一样。让我们来分析一下改动之后效率：如果比较一次，字符不匹配时将多移动模式窗口一个字符位置（这是大概率事件），如果不比较，按照Ｓｕｎｄａｙ算法移动模式窗口一个字符位置，需要的执行步数，首先要判断对应位置字符是否匹配（需要比较１次），不匹配（大概率事件），则先判断是否属于坏字符，需要ｍ次比较，如果不是坏字符，再查在模式串中的位置，查位置平均需要ｍ／２次，才决定移动字符数（最多ｍ个字符，最少１个字符，平均（ｍ＋１）／２个字符，各种情况下总比较次数为１＋ｍ＋ｍ／２，除以平均次数（ｍ＋１）／２，大约为３，也就是平均移动一个字符，比较要３次）；而改进后的算法，基本上属于移动一次，需要比较一次（大概率事件），这样就显著提高了算法效率。针对图１，Ｓｕｎｇｄａｙ算法第２次匹配和Ｚｈｕｓｕｎｄａｙ算法第２次匹配面临相同的情况，两算法却做出了不同操作，Ｚｈｕｓｕｎｄａｙ算法第２次匹配多向右移动了一步，导致最后算法效率的不同。同样的情况发生
３
１
１
博看网 . All Rights Reserved.
在（２）Ｃ情况下，这里也对Ｓｕｎｄａｙ算法进行了改进；这时也向左多判断一个字符，多数情况下也会让匹配窗口多向右移动一步。在本示例中，以上算法的改动让Ｚｈｕｓｕｎｄａｙ算法匹配次数比Ｓｕｎｄａｙ算法少了一次。
３　算法实现
根据上面的算法分析，采用Ｃ语言实现了Ｚｈｕｓｕｎｄａｙ算法，该算法整体采用循环结构，首先是双分支，分出前面叙述的（１）和（２）２种情况１）又分成Ａ和Ｂ２种情况，在Ｂ情况下，再向前判断，又分２种情况：①不匹配，模式窗口前进多增加１字符；②匹配，模式窗口按照原来Ｓｕｎｄａｙ算法计算的步长移动；
２）又分成Ｃ和Ｄ２种情况，和上面的叙述一致，下面是Ｃ语言的实现该算法的源程序，相关注释进行了说明。
ｉｎｔｚｈｕｓｕｎｄａｙ（ｃｈａｒ Ｔ，ｃｈａｒ ｐ，ｉｎｔｐｏｓ）／／ｐｏｓ是Ｔ中下标开始位置，主体算法
｛ｉｎｔＴｉｎｄｅｘ＝ｐｏｓ＋ｌｅｎｇｔｈＰ－１；
ｉｎｔｐｉｎｄｅｘ＝ｌｅｎｇｔｈＰ－１；
／／Ｔｉｎｄｅｘ是在Ｔ中搜索的当前位置，采用从右向左探索
ｉｎｔｐｉｐｅｉｐｏｓ；
ｗｈｉｌｅ（Ｔｉｎｄｅｘ≤ｌｅｎｇｔｈＴ－１）／／遍历源串Ｔ
｛
ｐｉｐｅｉｃｉｓｈｕ＋＋；／／２种情况１和２．
ｉｆ（Ｔ［Ｔｉｎｄｅｘ］！＝ｐ［ｐｉｎｄｅｘ］）／／不匹配模式串ｐ最后一个字符，有２种情况，分别是１和２．｛ｉｆ（ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］＝＝ｌｅｎｇｔｈＰ）／／１Ａ：目标字符不在模式串中，是坏字符；ｄｉｓｔ是模式串预处理数组，对０～１２７的ＡＳＣＩＩ字符能使模式窗口向右移动距离进行了预先统计。
ｉｆ（Ｔ［１＋Ｔｉｎｄｅｘ］！＝ｐ［０］）／／多验证坏字符左侧的一个字符。
Ｔｉｎｄｅｘ＋＝ｌｅｎｇｔｈＰ＋１；／／跳跃模式串长度个字符探索，验证成功比坏字符多跳一个。
ｅｌｓｅ／／验证不成功，跳跃模式串长度个字符。
Ｔｉｎｄｅｘ＋＝ｌｅｎｇｔｈＰ；
ｅｌｓｅ／／１Ｂ：改进处：目标字符在模式串中，但不是模式串最后一个字符；
｛ｉｎｔｘ＝ｌｅｎｇｔｈＰ－２－ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］；／／ｘ是由右向左第一次不匹配时字符的下标，因为没有全匹配，其值不能小于０．
ｉｆ（ｐ［ｘ］！＝Ｔ［Ｔｉｎｄｅｘ－１］＆＆ｘ＞＝０）
Ｔｉｎｄｅｘ＋＝ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］＋１；
ｅｌｓｅ／／这种情况多数不成立（而Ｓｕｎｄａｙ算法假定这里始终成立）。
Ｔｉｎｄｅｘ＋＝ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］；
｝
｝
ｅｌｓｅ／／２：匹配模式串的最后一个字符，回溯追查，对应２种情况，分别是Ｃ和Ｄ．
｛ｐｉｐｅｉｐｏｓ＝ｑｕａｎｐｉｐｅｉ（Ｔ，ｐ，Ｔｉｎｄｅｘ，ｌｅｎｇｔｈＰ－１）；／／从最后一个字符向前进行匹配
ｉｆ（ｐｉｐｅｉｐｏｓ！＝０）／／Ｃ：由后向前部分字符匹配，没有全匹配。这里也对Ｓｕｎｄａｙ进行了改进。
｛ｉｎｔｘ＝ｌｅｎｇｔｈＰ－２－ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］；
／／ｘ是由右向左最后一次匹配的字符左侧的字符的下标，因为没有全匹配，其值不能小于０．ｉｆ（ｐ［ｘ］！＝Ｔ［Ｔｉｎｄｅｘ－１］＆＆ｘ＞＝０）
Ｔｉｎｄｅｘ＋＝ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］＋１；／／多移动
ｅｌｓｅ
Ｔｉｎｄｅｘ＋＝ｄｉｓｔ［Ｔ［Ｔｉｎｄｅｘ］］；
｝
ｅｌｓｅ／／Ｄ：所有字符全匹配。
ｒｅｔｕｒｎＴｉｎｄｅｘ－ｌｅｎｇｔｈＰ＋１；／／返回匹配的起始下标。
｝
｝
ｉｆ（Ｔｉｎｄｅｘ＞＝ｌｅｎｇｔｈＴ）／／匹配结束，依然没有返回，表示未匹配成功。
ｒｅｔｕｒｎ－１；
｝
４　实验结果评测
为了评测该算法的性能，对算法运行的匹配次数和语句执行次数进行了比较。针对图１和图２列举的情
况，两算法运行结果显示如图３，程序对前面的实例进行了验证，得出了Ｓｕｎｄａｙ算法匹配５次和Ｚｈｕｓｕｎｄａｙ匹配４次的结果；同时，在两算法的执行语句的位置旁都添加了全局变量ｃｏｕｎｔ的自增语句作为计数器，来统计两者时间复杂度的依据，运行结果显示，优化后的Ｚｈｕｓｕｎｄａｙ执行了１７步，Ｓｕｎｄａｙ算法执行了２５步，是原算法执行步数的６８％，同时针对不同数据进行了多次验证，结
４
１
１        　西安科技大学学报          　２０１６年　博看网 . All Rights Reserved.
第１期朱宁洪：字符串匹配算法Ｓｕｎｄａｙ的改进果都显示Ｚｈｕｓｕｎｄａｙ优于Ｓｕｎｄａｙ算法，特别是针对模式串Ｐ后缀在文本串Ｔ重复率高的情况，优化比率更明显。由于该实例Ｔ中大量包含模式串Ｐ中的字符，Ｚｈｕｓｕｎｄａｙ的执行次数在１ １ｎ左右，达到１７次；Ｓｕｎｄａｙ执行次数为１ ７ｎ左右，达到２５次。在实际中经过大量测试，在坏字符大量存在的情况下，二者的时间复杂度逐渐接近Ｏ（ｎ／ｍ），基本一致，但Ｚｈｕｓｕｎｄａｙ算法的执行次数始终优于Ｓｕｎｄａｙ算法，Ｚｈｕｓｕｎｄａｙ算法的执行次数约为Ｓｕｎ ｄａｙ算法执行次数的６５％～８０％之间，效率提高２５％～５０％．限于篇幅，更多的比较结果这里不再
一一列举显示结果。
图３　２种算法比较程序运行结果
Ｆｉｇ．３　Ｃｏｍｐａｒｉｓｏｎｏｆｔｗｏａｌｇｏｒｉｔｈｍｐｒｏｇｒａｍｒｅｓｕｌｔｓ
５　结　论
文中针对当前研究的热点字符串匹配算法（Ｓｕｎｄａｙ算法），提出了改进的算法Ｚｈｕｓｕｎｄａｙ，并对两者算法进行了分析和实现，并通过实验验证了Ｚ
ｈｕｓｕｎｄａｙ优于Ｓｕｎｄａｙ算法。经过大量实际测试，在坏字符大量存在的情况下，Ｚｈｕｓｕａｎｄａｙ算法能达到Ｏ（ｎ／ｍ）的时间复杂度，且Ｚｈｕｓｕｎｄａｙ算法的效率比Ｓｕｎｄａｙ算法提高２５％～５０％．参考文献  Ｒｅｆｅｒｅｎｃｅｓ
［１］　潘冠桦．单模式字符串匹配算法效率的研究［Ｄ］．太
原：太原理工大学，２０１３．
ＰＡＮＧｕａｎ ｈｕａ．Ｒｅｓｅａｒｃｈｏｎｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｓｉｎｇｌｅｍｏｄ
ｅｓｔｒｉｎｇｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍ［Ｄ］．Ｔａｉｙｕａｎ：ＴａｉｙｕａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，２０１３．
［２］　孙艺珍，季小迪，张京涛．基于．Ｎｅｔ的全文搜索引擎
设计与实现［Ｊ］．西安科技大学学报，２０１４，３４（６）：７０１．
ＳＵＮＹｉ ｚｈｅｎ，ＪＩＸｉａｏ ｄｉ，ＺＨＡＮＧＪｉｎｇ ｔａｏ．Ｄｅｓｉｇｎａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｆｕｌｌｔｅｘｔｓｅａｒｃｈｅｎｇｉｎｅｂａｓｅｄｏｎ．Ｎｅｔ
［Ｊ］．ＪｏｕｒｎａｌｏｆＸｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈ ｎｏｌｏｇｙ，２０１４，３４（６）：７０１．
［３］　马　莉，李树刚，肖　鹏，等．云计算环境下煤矿应急
管理海量数据存储技术［Ｊ］．西安科技大学学报，２０１４，３４（５）：５９６．
ＭＡＬｉ，ＬＩＳｈｕ ｇａｎｇ，ＸＩＡＯＰｅｎｇ，ｅｔａｌ．Ｍａｓｓｄａｔａｓｔｏｒ ａｇｅｔｅｃｈｎｏｌｏｇｙｏｆｃｏａｌｍｉｎｅｅｍｅｒｇｅｎｃｙｍａｎａｇｅｍｅｎｔｉｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．ＪｏｕｒｎａｌｏｆＸｉ’ａｎＵ ｎｉｖｅｒ
ｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１４，３４（５）：５９６．［４］　李军民，李立博．人工鱼和蒙特卡罗混合算法的应
用［
Ｊ］．西安科技大学学报，２０１４，３４（２）：２２４．ＬＩＪｕｎ ｍｉｎ，ＬＩＬｉ ｂｏ．ＡｐｐｌｉｃａｔｉｏｎｏｆａｒｔｉｆｉｃｉａｌｆｉｓｈｓｗａｒｍａｎｄＭｏｎｔｅＣａｒｌｏｈｙｂｒｉｄａｌｇｏｒｉｔｈｍ［Ｊ］．ＪｏｕｒｎａｌｏｆＸｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１４，３４（２）：２２４．
［５］　巫喜红，凌　捷．基于字符频率的字符串模式匹配算
法的研究［Ｊ］．制造业自动化，２０１３，３５（９）：１１－１４．ＷＵＸｉ ｈｏｎｇ，ＬＩＮＧＪｉｅ．Ｒｅｓｅａｒｃｈｏｎｓｔｒｉｎｇｐａｔｔｅｒｎｍａｔｃ ｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｈａｒａｃｔｅｒｆｒｅｑｕｅｎｃｙ［Ｊ］．Ｍａｎｕ ｆａｃｔｕｒｉｎｇＡｕｔｏｍａｔｉｏｎ
，２０１３，３５（９）：１１－１４．［６］　许元飞基于纹理的图像检索算法研究［Ｊ］．西安科
技大学学报，２０１３，３３（４）：４７０．
ＸＵＹｕａｎ ｆｅｉ．Ｒｅｓｅａｒｃｈｏｎｔｅｘｔｕｒｅｂａｓｅｄｉｍａｇｅｒｅｔｒｉｅｖａｌａｌｇｏｒｉｔｈｍ［Ｊ］．ＪｏｕｒｎａｌｏｆＸｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１３，３３（４）：４７０．
［７］　徐　珊，袁小坊．Ｓｕｎｄａｙ字符串匹配算法的效率改进
［
Ｊ］．计算机工程与应用，２０１１，４７（２９）：９６－９８．ＸＵＳｈａｎ，ＹＵＡＮｘｉａｏ ｆａｎｇ．ＥｆｆｉｃｉｅｎｃｙｉｍｐｒｏｖｅｍｅｎｔｏｆＳｕｎｄａｙｓｔｒｉｎｇｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍ［Ｊ］．Ｃｏｍｐｕｔｅｒｅｎｇｉ ｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎ，２０１１，４７（２９）：９６－９８．［８］　潘冠桦，张兴忠．Ｓｕｎｄａｙ算法效率分析［Ｊ］．计算机应
用，２０１２，３２（１１）：３０８２－３０８４．
ＰＡＮＧｕａｎ ｈｕａ，ＺＨＡＮＧＸｉｎｇ ｚｈｏｎｇ．ＥｆｆｉｃｉｅｎｃｙａｎａｌｙｓｉｓｏｆＳｕｎｄａｙａｌｇｏｒｉｔｈｍ［Ｊ］．ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ，２０１２，３２（１１）：３０８２－３０８４．
［９］　冯川放．规则引擎技术的可配置ＥＯＳ平台的设计与
实现［
Ｊ］．西安科技大学学报，２０１３，３３（３）：３５３．ＦＥＮＧＣｈｕａｎ ｆａｎｇ．Ｄｅｓｉｇｎａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｃｏｎ ｆｉｇｕｒａｂｌｅＥＯＳｐｌａｔｆｏｒｍｆｏｒｒｕｌｅｅｎｇｉｎｅｔｅｃｈｎｏｌｏｇｙ［Ｊ］．ＪｏｕｒｎａｌｏｆＸｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１３，３３（３）：３５３．
［１０］李明月，张善卿，陆剑锋，等．一种改进的Ｓｕｎｄａｙ匹配
算法［Ｊ］．杭州电子科技大学学报，２０１５，３５（１）：９３－９７．
ＬＩＭｉｎｇ ｙｕｅ，ＺＨＡＮＧＳｈａｎ ｑｉｎｇ，ＬＵＪｉａｎ ｆｅｎｇ，ｅｔａｌ．ＡｎｉｍｐｒｏｖｅｄＳｕｎｄａｙｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍ［Ｊ］．ＪｏｕｒｎａｌｏｆＨａｎｇｚｈｏｕＥｌｅｃｔｒｏｎｉｃａｎｄＳｃｉｅｎｃｅＵｎｉｖｅｒｓｉｔｙ，２０１５，３５（１）：９３－９７．
５
１１      博看网 . All Rights Reserved.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。