摘要：学生的文本作业以及程序代码中存在很多抄袭现象，这种现象使得学习积极性降低，教学效率难以提高。传统的人工查重费时费力，效率很低。不过随着现代计算机技术的高速发展，使用程序代码查重能够极大的提高检测抄袭的准确率。使用结构度量法进行查重检测需要标记匹配，串匹配算法的优劣决定了查重过程的快慢，寻求适用于代码查重的高效串匹配算法是目前研究的重点及难点。

本文首先介绍经典的串匹配算法，包括KMP算法，BM算法以及KR算法，然后研究几种代码查重检测序中常用的串匹配算法，包括LCS算法，动态程序设计法，Heckel算法和GST算法，给出了这些算法的基本思想，最后对这些算法在程序代码查重中的优缺点进行比较分析，并对LCS与GST进行算法实现。

关键词：程序查重；串匹配算法；KMP算法；GST算法

Abstract：Students in the text of the operation and the code there are many plagiarism phenomenon, this phenomenon makes learning enthusiasm to reduce the teaching efficiency is difficult to improve. Traditional manual inspection time and effort, efficiency is very low. However, with the rapid development of modern computer technology, the use of program code check can greatly improve the accuracy of detection plagiarism, string matching algorithm is an important algorithm in the code check, so string matching algorithm The key to the speed of the whole process, to find a more simple and fast string matching algorithm has become the current research problems faced.

In this paper, we first introduce some classical string matching algorithms, including KMP algorithm, BM algorithm and KR algorithm, and then introduce several improved string matching algorithms, including LCS algorithm, dynamic programming method, Heckel algorithm and GST algorithm, Understand the basic ideas of these algorithms, and analyze the advantages and disadvantages of these algorithms in the code check and implement the LCS algorithm and GST algorithm.

Keywords: program check; string matching algorithm；KMP algorithm；GST algorithm

目录

第一章绪论-1

1.1研究背景及意义-1

1.2研究现状1

1.3主要研究内容2

第二章串匹配的经典算法3

2.1前缀搜索3

2.1.1KMP算法-3

2.1.2KR算法4

2.2后缀搜索7

2.2.1BM算法-7

第三章查重程序中常用的串匹配算法10

3.1Shift-And/Shift-Or算法10

3.2Horspool算法11

3.4LCS算法12

3.5动态程序设计13

3.6Heckel算法14

3.7GST算法-14

3.8LCS与GST算法实现分析-16

3.9本章小结-17

结论-19

致谢-20

参考文献-21

第一章绪论

1.1研究背景及意义

学生在程序类作业或者文本作业中的抄袭严重影响了教学效果，所以抄袭检测并对学生进行一定惩罚，会一定程度上减少抄袭。如果仅仅依靠人工查重，那么这将是一项很繁重的工作，不仅费劲而且效率很低，这时就需要用到程序代码进行检测。串匹配算法主要用于解决模式搜索问题，在文字编辑处理、图像处理及文件搜索等领域有着广泛的应用，是程序代码查重中的重要算法。

串匹配是计算机科学中最古老、研究最广泛的问题之一，并且，在很多应用中也可以见到串匹配的身影。在最近的一些学术报刊中，我们可以发现学术界对于串匹配问题的研究日益加深，他们的研究大多集中在在发展迅猛的信息检索领域和计算生物学领域。之所以出现上述现象，不仅是因为在这两个研究领域中需要处理的文本规模变得越来越大，更关键的是需要在规模很大的文本中进行越来越复杂的搜索。所以寻找思想简单、实际应用效果好的算法就成了研究的热点问题。

1.2研究现状

1.3主要研究内容

本文主要研究串匹配经典算法和在查重程序中常用的一些改进的串匹配算法。本文整体结构如下：