文档介绍：字符串模式匹配算法综述
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
字符串模式匹配算法综述
摘要：BF 算法、KMP 算法、BM 算法、BMH 算法、AC 算法和 AC—BM 算法.
关键词：模式匹配，BF算法，KMP算法,改进算法，BM算法，AC算法,ACH算法。
字符串是一种线性表，它在计算机应用系统中如文本编辑、情报检索、。设Pattern（下文简称 P）和Text（下文简称 T)是给定的两个字符串，在字符串T中寻找等于P的子串的过程称为模式匹配,其中字符串T称为主串,，则称匹配成功，否则匹配失败。比较著名的模式匹配算法有BF算法、KMP算法、AC算法和BM算法，本文对所述算法进行探讨。随着计算机技术的快速发展,计算机网络在国民经济中发挥了日益重要的作用，，网络安全也日益引起人们的关注。
1。模式匹配算法
1。1 单模式匹配算法
BF（Bruce Force）算法
算法思想
从文本字符串 T的第一个字符起和模式字符串 P 中的第一个字符开始比较，若相等，逐个比较后续字符,否则从文本字符串的下一个字符起再重新和模式字符串的第一个字符比较。
算法描述
对于文本字符串
3
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
模式字符串
（1）P 和 T 从左端对齐,使得 与 对齐；
(2)从左到右匹配 P 与 T 的字符，直到出现不匹配的情况,则执行（3），或是 P 己被完全匹配的情况则结束比较；
（3）将 P 右移一个字符,重新从P的第一个字符开始匹配;
（4）重复上述（2)过程，直到 P 被完全匹配,或 P 移到 T 的右端.
KMP（Knuth Morris Pratt)算法
KMP 算法是 Knuth 等人在 BF 算法的基础上提出来的。从本质上讲，KMP算法就是出现不匹配情况下带有智能指针初始化的 BF 算法。为了在不匹配时重新定位指针，KMP 算法需要进行预处理算出一个 next数组来。
KMP 算法利用己匹配成功部分的信息，即前缀（模式字符串中存在的相同子串),可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯.
算法描述
当模式匹配执行到比较字符 和,其中 l=i=n，l=j=m。
（l)若 =则继续往右做匹配检测，即对 和 进行匹配检测.
（2）若 当 j=l，则对 和 进行匹配检测，即把模式和正文向右移动一位再从模式的第一个字符进行匹配;若 l<j=m,我们将试图在模式中找到一个合适位置再进行比较,我们把这个下标记做 next[j]。执行和的匹配，其中 next［j]的构造是算法的核心，约定如下：
4
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
改进的字符串匹配算法
字符串模式匹配算法要解决的关键问题是：在模式与文本在某个位置比较失败时，如何使模式串窗口向右移动最佳距离，尽量多的跳过不必要比较的字符，减少匹配的次数,并使产生这种距离的算法复杂度降低和易于理解。通过对现有的各种字符串匹配算法进行分析研究,我们提出一种改进算法,该算法简单实用,便于理解。
1。基本思想
与KMP算法类似,在模式串的匹配过程中,字符比较采用符合人们****惯的从左到右顺序，模式