串匹配算法c++实现string matching algorithm BF,BM,KMP,SHIFT_AND,SHIFT_OR...

在分析Wu-Manber算法的基础上 ,结合QS算法思想,设计了一种改进的多模式串匹配算法: QWM( quick Wu-Manber)。算法充分利用紧邻当前窗口之后的 B字符块,使算法的最大移动距离由原来的( m-B+1)增大至 (m+B) ,平均移动距离也得到很大提高。同时对QWM算法和Wu-Manber算法进行了实验对比,无论模式串数量 和最小长度怎么变化,性能都有较大提升。实验表明,改进的算法在对英文文本进行扫描时有4%～13%的提高。

串匹配（String Matching）问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。 串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配（Keyword Matching）。所谓关键词匹配，是指给定一个长为n的文本串T[1，n]和长为m的模式串P[1，m]，找出文本串T中与模式。