基于后缀树的代码抄袭检测：KR算法在C语言程序中的应用

"本文介绍了使用后缀语法树进行代码抄袭检测的研究，特别是针对C语言程序，通过构建和优化后缀树，以及应用KR算法计算代码的相似度。这种方法将函数作为匹配计算的基本单元，以查找最大匹配子串。" 在程序抄袭检测领域，后缀语法树是一种有效的工具。在描述的系统中，它首先在初始化阶段清除残留文件，确保系统运行的清洁。接着，系统进入源代码预处理模块，这个模块的核心任务是构建和优化后缀树。源代码经过词法和语法分析，形成后缀树，通过ANTLR预留的接口，工厂模式用于去除冗余信息，生成优化后的后缀树字符串序列。 相似度计算模块是系统的关键部分，它利用KR算法来计算两个程序对（A和B）之间的相似度。该算法以函数为单位，分别读取优化后的后缀树文件，拆分成多个字符串。每个字符串的长度为MML（最大匹配长度），并计算它们的散列值，存储在数组Ahasharray和Bhasharray中。通过比较两个散列值数组，找到相同的散列值，记录对应的子串初始位置，并逐个字符比较两个子串，扩展匹配直到达到最大匹配或遇到不匹配。算法的结果是所有最大匹配的集合及其长度。 整个流程如下： 1. 清除默认目录下的临时文件。 2. 使用ANTLR生成的分析器对源代码进行词法和语法分析，构建后缀树。 3. 去除后缀树的冗余信息，得到优化的后缀树字符串序列。 4. 以函数为单位拆分字符串，计算散列值。 5. 使用KR算法比较两个程序的散列值，找到相同散列值的子串并进行逐字符匹配，找出最大匹配子串。 6. 记录最大匹配集合的长度和。 这种方法的优势在于，它可以有效地检测代码中的相似性和潜在的抄袭行为，特别是在C语言程序中，由于函数级别的匹配，能够更准确地定位抄袭的部分。 此外，这篇硕士论文还强调了抄袭问题在信息技术发展背景下日益严重，尤其是在程序设计课程作业中。因此，研究和开发高效的抄袭检测方法对于维护学术诚信至关重要。论文作者基于ANTLR制定了C语言文法文件，生成解析器，为后缀树的构建打下基础，这展示了在实际应用中解决这一问题的可行路径。