字符串匹配算法是计算机应用、信息检索及计算生物学等的重要研究内容,在日常生活及科学研究中有着广阔的应用。随着计算机技术和网络技术的发展,新的应用对匹配实时性的要求不断提高。本文在对精确字符串匹配问题的研究与现状及其各种方法进行深入探讨的基础上,针对单模式精确字符串匹配及多模式字符串匹配中,被广泛使用的BM和WM两种算法进行深入系统的研究,并提出相应的改进算法并通过实验验证了新算法的优越性。全文主要内容如下:1.分析了字符串匹配算法的国内外研究现状,详细讨论了精确字符串匹配下的三种搜索方式,研究并实现了单模式字符串匹配及多模式字符串匹配下的若干典型算法,包括Shift-And及Shift-Or算法、Horspool算法、BNDM及BOM算法、AC算法、WM算法、SBOM算法。2.传统的BM算法在不匹配发生时,匹配窗口移动的最大距离较小并且匹配窗口能够移动的最大安全距离也不够大。因此,字符串匹配速度仍有提升空间。针对这种情况,本文提出了一种新的可以增加平均移动距离的改进的BM算法。该算法首先在预处理阶段使用任意的两个字符作为字符块来计算移动距离,并设置最大移动距离为模式串长度加一;然后在查找阶段通过比较连续的两个字符块来增加大距离移动的概率。实验结果表明该算法相比于原算法在速度性能上提高明显。3.传统的WM算法在发生不匹配时安全移动距离明显较小,而当与模式串匹配后的移动距离又较保守,并且存在单次匹配而整个模式串不匹配的概率较大的情况。针对这些问题,本文提出了一种新的改进的WM算法,该算法首先对SHIFT表进行改进,使得安全移动的距离有了较为明显的提高;其次改进搜索查找算法,通过增加比较字符块使得单次匹配而整个模式串不匹配的概率下降并使与模式串匹配后的移动距离不再为1。实验表明,本算法较原算法在匹配速度上具有较好的实验效果。