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

作　　者：徐黎明[1] 

机构地区：[1]北京物资学院,北京101149

出　　处：《内蒙古科技与经济》2016年第7期87-89,共3页Inner Mongolia Science Technology & Economy

基　　金：北京物资学院2015年教改项目

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

关 键 词：近似匹配 GST算法 KMP算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]