近年来，计算机技术高速发展，文本规模不断变大，而信息检索领域需要对不断增大规模的文本进行越来越复杂的搜索，所以非标准的模式匹配问题就应运而生，包括通配符，近似匹配等等。通配符能够简化问题定义，但同时也增加了复杂性。

国外对于程序查重的研究比较早，目前也有了多个成熟的查重检测系统，如Jplag，MOSS和YAP等[1]，这些系统能够很好的应用于学生程序以及文档作业的检测中。

国内对于这方面的研究也在不断取得进展，如内蒙古大学计算机学院实现的查重检测系统，使用的是GST串匹配算法进行匹配，计算相似度，即重复率。国内也有研究者根据文本相似性对来源进行分析，这种方式不仅可以检测重复，也能对文本来源进行分析。

而串匹配算法在这些查重系统中扮演着至关重要的角色。简单来说，串匹配算法的作用就是给定一个片段，然后在文本或者程序中寻找与之匹配或者相似的片段。而查重系统就将各个匹配或相似片段结合起来，通过计算求得整个文本或程序的重复相似度。而寻找匹配的过程占据着程序查重的大部分时间，所以一个好的串匹配算法对于查重系统十分关键，包括LCS算法，GST算法都被应用于这类系统中。

设计算法时不仅需要考虑时空效率，同时也要保证匹配结果的完整。在串匹配研究领域都知道算法的思想越简单，那么算法在实际应用中的效果越好。一些新的位并行技术也随着计算机技术的发展而产生。

在众多串匹配算法中，KMP算法的地位不可替代，现今的众多串匹配算法大都是对KMP算法以及BM算法进行改进后得到的，在文本检索以及生物信息学等领域都有很好的应用。

参 考 文 献

[1] L.Prechelt，G.Malphol and M.Phippsen. Finding Plagiarisms among a Set of Programs with Jplag. Journal of Universal Computer Science，2002，8(11)：1016-1038

[2] 刘燕兵，刘萍，谭建龙，郭莉. 基于存储优化的多模式串匹配算法. 计算机研究与发展，2009，46(10)：1768-1776

[3] 李韦男，虞慧群. 一种改进的BM字符串匹配算法. 计算机工程与应用，2014,50(16)：104-108

[4] 张量，刘秀敏，刘秀娟. Winnowing算法和动态规划算法在作业剽窃检测中的应用和比较. 计算机工程与科学，2009,31(6)：147-149

[5] 袁华鹏，蔡军，葛家翔. 用多模式匹配的方法设计基于网络的IDS. 计算机工程，2002，28(2)：26-28

[6] 沈州，王永成，刘功申. 改进的中文字串多模式匹配算法. 情报学报，2002，21(1)：27-32

[7] 王永成，沈州，许一震. 改进的多模式匹配算法. 计算机研究与发展，2002，39(1)：13-17

[8] 王建国，郑家恒. BM串匹配算法的一个改进算法. 计算机工程与科学，2007,29(5)：94-95

[9] 蒋文沛. 对字符串模式匹配KMP算法的探讨. 南宁师范高等专科学校学报，2001，3(2)：10-14

[10] 王锋. BM串匹配算法与改进算法的研究. 福建电脑，20010，26(7)：77-79

[11] Jiang Y，Li G，Feng J，et，al. String similarity joins：An experimental evaluation. Proceedings of the VLDB Endowment，2014,7(8)：625-636

[12] 李欣，舒风笛. 最长公共子序列问题的改进快速算法. 计算机应用研究，2000，4(2)： 28-30

[13] Li G，Deng D，Wang J，et al. Pass-join：A partition-based method for similarity joins. Proceedings of the VLDB Endowment，2011,5(3)：253-264

[14] Ukkonen E. Finding approximate patterns in strings. Journal of algorithms，1985，6(1)：132-137

[15] 刘雨心，孟亮，窦银科. 一种改进的Sunday字符串匹配算法. 太原理工大学学报，2013,44(5)：604-607

[16] Schulz K U，Mihov S. Fast string correction with Levenshtein automata. International Journal on Document Analysis and Recognition，2002,5(1)：67-85