字符串匹配算法的研究
及其程序实现
计算机学院
计算机科学与技术专业
2007
级指导教师：滕云
摘要：在字符串匹配算法之中，最古老和最著名的是由
D.E. Knuth
, J. h. Morris, V. R. Pratt
在1997
年共同提出的
KMP算法。直至今日，人们对字符串匹配问题还
在进行着大量的研究，以寻求更简单，或者平均时间复杂度更优的算法
;学者们在不同的研究方向上，设计出了很多有效的匹配算法。在现实生活中，串匹配技术的应用十分广泛，其主要领域包括：入侵检测，病毒检测，信息检索，信息过滤，计算生物学，金融检测等等。在许多应用系统中，串匹配所占的时间比重相当大，因此，串匹配算法的速度很大程度上影响着整个系统的性能。
该论文重点分析了
KMP算法的实现原理和
C语言实现，并在此基础上提出了改进的
KMP算法，使得该算法更方便实用。
关键词：KMP算法；时间复杂度；串匹配；改进；方便使用；
String matching algorithm
and Implementation of the Program
College
ofComputer
Sciences
,Com ...