字符串相似度度量中LCS和GST算法比较

就字符串相似度度量算法的LCS和GST在概念、实现、效率方面进行比较分析,简要探讨了两种算法的应用领域。

基于GST字符串近似匹配算法的研究

GST算法作为字符串近似匹配的经典算法,被广泛应用于防剽窃系统中,而针对匹配信息量大,GST算法效率严重下降的问题,提出了一种基于KMP算法的改进算法,该算法主要是在scanpattern阶段对GST算法进行改进,同时融合了传统GST算法局部最大存储技术,从理论分析KMPGST算法所需要的时间可以从最初的O(n^3)提高到O(m+n)的线性时间,并通过实验验证改进后的KMP-GST算法的执行效率明显高于GST算法和RKR-GST算法。

程序代码抄袭检测中串匹配算法的研究

为了保证程序设计课程实践教学质量,避免学生抄袭,可以检测学生的源程序,代码的相似度是抄袭检测的关键技术。文章介绍了一种串匹配算法——GST算法,包括GST算法的核心思想以及伪代码实现。