字符串的模式匹配算法——基于KMP算法的讨论

重点对基本的串匹配算法和KMP算法进行了探讨。通过对这两种算法的比较分析提出了一个新算法，此算法具有比基本的串匹配算法更优越的时间复杂性，并且相对KMP算法而言更简洁易懂。     

网络入侵检测系统模式匹配算法性能分析

模式匹配算法对于网络入侵检测系统起着非常重要的作用，直接影响着检测系统的准确性与实时性。本文对BF，KMP，BM和Karp—Rabln算法进行了性能分析，通过实验数据进行了验证，并对适合IDS的模式匹配算法提出了改进意见和思路。     

模式匹配算法的深入研究

模式匹配算法的应用较为广泛,KMP算法是一种性能较高的算法,所以对KMP算法的深入研究能够使模式匹配问题得到较大的改善．在匹配的过程中,从模式匹配算法的子串滑动出发,解决特殊的实际问题．通过特殊子串滑动算法与KMP算法整合的实践,在一定程度上省略了KMP函数的求解过程,提高了模式匹配问题的工作效率,保证了模式匹配问题的具体划分．     

一种改进的KR模式匹配算法

在分析BF、KMP和KR等模式匹配算法的基础上提出一种改进的KR算法(IKR),在产生哈希冲突时利用双向比较法进行匹配.实验结果表明,该算法可以快速有效地进行模式匹配.     

几种模式匹配算法的效率分析

分析几种模式匹配算法如KMP、BM、RK、SO。通过上机实验对这些算法的匹配时间进行测试,结果表明在这些模式匹配算法中BM算法是速度最快效率最高的算法。     

基于模式匹配KMP算法的探讨

模式匹配是一种重要的非数值运算,本文对字符串模式匹配算法BF与KMP进行了详细地分析,介绍一个KMP新算法,相对KMP算法而言更简洁易懂。     

线性平移策略降低算法复杂度的研究与实践

平移策略在线性算法研究中具有广泛的使用价值,主要的应用方法为相对定长平移和线性段整体平移两种策略,应用平移策略可以对算法以及算法的特定部分进行改进,从而降低算法复杂性,提高运行效率.主要以计算机专业硕士研究生考试和经典KMP算法为案例,通过实验比较得出最优算法的过程.     

对KMP算法中模式串所构造自动机的改进

对发生失配现象时KMP算法中模式串所构造自动机的处理过程进行了分析，指出了其中状态函数的向后处理存在不足，并对此进行了相应的改进．     

一种改进的KMP高效模式匹配算法

针对KMP算法存在着主串与模式串中多个相同字符重复比较的缺陷,在KMP算法的基础上,给出了一种新的模式匹配算法,该算法不像KMP算法那样向左滑动模式串的指针,而是每次比较字符不匹配时,根据模式串当前字符的特征值k,使主串的指针向前跳跃k个值,且使模式串的指针置于起始位置,开始新一轮的匹配,加快了主串的匹配速度．理论分析和试验证明,该算法需要的比较次数比KMP算法减少将近一半．     

KMP的多种计算方法

通过对串的前缀、后缀、交迭的介绍，引出了对失败函数的求解，解决了KMP算法中匹配串的移动问题，并提出了各种计算方法．该方法和传统的KMP算法的时间复杂度都为O(m n)．     

字符串匹配算法探讨

分析了BM和KMP算法特点,阐述了字符串匹配算法在文本处理领域、信息检索、语义学、分子生物学等学科中应用的意义,对字符串中最有影响的KMP算法、BM算法、RK随机算法和SUANDAY算法以及由此而产生的一些改进算法进行研究,实现了实验分析及功能对比,并指明各算法的适用性.     

基于MPI的两种数据分组方式的KMP算法的实现

通过对KMP算法的研究,确定了基于MPI的KMP算法实现的可能性.主要重点是分析了MPI环境下KMP算法中目标串分组2种方式,第1种是把目标串进行平均的不重叠的分组,第2种上把目标串以模式串长度为重叠单位进行分组.并对初步的实验结果进行了分析.     

适合中文的双向比较模式匹配算法

分析了几种常用的模式匹配算法,提出一种适合于中文的基于KMP的改进算法,即双向比较模式匹配算法.该算法以KMP算法为基础,引入特征数组以记录模式串尾字符在模式串中出现的位置信息,从而获得模式串在匹配过程中的最大移动距离和最少比较次数.实验结果表明,双向比较模式匹配算法可有效降低匹配次数.     

单模式精确匹配算法研究

模式匹配算法在各领域中有重大的应用价值。文章详细分析了BF、KMP、BM、Tuned BM和QS 5种单模式精确匹配算法;通过上机实验,采用不同的模式串长度对这些算法的匹配次数、比较过的字符个数和所需时间3方面进行测试;结果表明,BM、Tuned BM、QS算法在实际运行性能相对较好;而Tuned BM算法可有效地减少字符比较次数,是其中时间复杂最优的算法。     

简化GNU编译器套件抽象语法树的算法研究

提出了一种消除抽象语法树文本中冗余的方法,借助Knuth-Morris-Pratt(KMP)算法,设计核心算法,对抽象语法树进行简化,并选出几个经典的代码片段进行实验,对算法的性能做了相应验证.实验结果表明,算法在消除冗余方面的简化率达到90%以上.     

关于KMP空间的一个注记

本文给出自反空间与KMP空间的乘积是KMP空间的一个简单证明,并提出若干问题。