串匹配算法是计算机科学领域中一个重要的基础研究领域。在文本处理、数据压缩、搜索引擎、生物计算,以及网络安全等大量的应用中,都需要进行串匹配。本文主要讨论精确模式串匹配,主要内容包括:首先对Linux内核中的TextSearch库进行了分析和研究,并且针对其缺陷和不足进行了改进,将TextSearch从内核中提取出来,形成了串匹配算法库LibTextSearch,并作为独立第三方开源库发布,该库运行于用户空间,同时向LibTextSearch库中添加了多种高效的串匹配算法,并简单介绍了这些算法的应用特点和使用场合,大大丰富了用户的选择范围。基于BNDM算法提出了LNDM算法,该算法使用交互重叠的宽窗口来扫描正文的思想,在窗口中先从中间位置往前扫描模式串的前缀,然后在右窗口中从前往后扫描模式串的后缀,最大化的挖掘出当前窗口中的有用正文信息,使得窗口在移动时损失的信息尽量小,提高了算法的效率,使得最差时间复杂度、最优时间复杂度和平均时间复杂度分别达到了理论最优结果O(n)、O(n/m)以及O(n logσ(m)/m)。性能测试实验也验证了他们的平均时间复杂度最优的结果,在查找短模式时,LNDM算法在大字母表情况下是最快的。本文还将BMA算法与Bit-Parallelism思想进行结合,提出了NBMA(Nondeterministic Boyer-Moore Automaton)算法,BMA算法使用BM自动机来进行字符串匹配,但是该自动机使用的状态数是模式串的指数函数,而NBMA使用Bit-Parallelism技术来模拟非确定的BMA,避免了BMA状态数大的问题,最后给出了实验结果。最后本文提出了一个字符串匹配算法的自动化测试平台,该平台采用一系列的自动化脚本来生成随机文本测试实验中用到的随机正文和随机模式信息,并可根据运行参数来自动化的进行模式匹配算法的测试实验,最后给出使用gprof程序得到的各个算法运行时间,方便了用户在随机文本情况下的测试字符串匹配算法过程。