2025年1月5日 第116页

在字符串匹配算法中，两种常用的方法是KMP算法和BM（Boyer-Moore）算法，它们的主要区别在于搜索模式串的方式。KMP算法的传统做法是从左到右逐字符匹配，而BM算法则引入了一种自右向左的扫描策略。这种改变使得算法在遇到正文中不存在于模式中的字符时，能够更快地跳过，从而提高匹配效率。

BM算法的核心在于设计一个函数d，它接收一个字符x作为输入，其值域为模式串W[1,m]中字符的索引集合{1,2, ..., m}。这个函数的作用是确定在模式中，给定的字符x可能存在的位置。通过预先计算d函数，算法可以根据正文中的字符直接找到模式中可能的匹配位置，避免了不必要的比较，显著提高了搜索速度。

kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。