引言字符串匹配是字符串的基本运算之一。串的模式匹配即子串定位，是一种重要的串运算。模式匹配就是在主串Ss1s2s3s4……中查找模式串Tt1t2t3t4……的所有出现，该技术在很多领域都发挥重要的作用，比如在情报检索、网络搜索、文本检索、拼写检查、语言翻译、数据压缩、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等各个方面都有着很重要的应用。通过模式匹配，我们可以得到很多我们想要知道的信息，而这些是靠人工难以完成的。尤其是在以后的段落搜索，自然语言查询中，对模式匹配的速度、效率等要求会越来越高，而传统的BF、KMP和BM等算法并不能很高效的给出结果，因此我们有必要对模式匹配的算法进行进一步发展。本文主要在介绍了BF算法、KMP算法的基础上提出一种更好的算法基于统计特征的模式匹配算法。
f1绪论我们在日常生活中经常以局部特征判定事物，而这种方式是普遍认可的，也是最佳的。一项将此技术应用于计算机科学领域的就是基于统计特征的模式匹配算法。11基于统计特征的模式匹配算法提出原因对于KMP、BM等算法有一个共同的特征：顺序扫描或者从左至右，或者从右至左。这样的好处是匹配时有顺序的规律可循，比较容易理解，操作起来比较方便，缺点就是没有最大限度利用模式自身的一些统计特征而只是利用了顺序的特征。如何利用统计特征呢？举个例子来证明。在街上我们遇到了一个似曾相识的人，我们判断那个人是不是我们认识的人的时候，我们是把遇到的那个人与我们记忆中的那个人的特征相比较，比如说秃顶，眼角有颗痔，身高，性别，胖瘦，脸型，肤色等等。我们比较是鲜明的特征，而不是从头到脚的扫描比较。也就是说我们在比较两个事物的时候是优先比较他们比较特殊的地方。对于模式匹配，这个优先级似的比较方式依然成立。12基本数据规定传统的算法分析在有了模式匹配的需要后，出现了很多模式匹配的算法，在这里为后续内容分析而规定：主串S的长度为
，模式串T的长度为m，子串的定位操作I
dexSTpos，其中pos为某个字符在主串中的位置。传统的模式匹配算法2传统的模式匹配算法本章介绍三种典型的传统的模式匹配算法，并分别给出部分算法实现。21BF算法BF（BruteForce）算法即简单模式匹配算法，也称朴素串匹配算法算法，其算法思想：对主串S和模式串T进行从左至右顺序匹配比较，若主串S的第一个字符和模式串T的第一个字符进行比较，若相等则同时向后移动一位，继续逐个比较后续字符，否则r