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

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