文件名称：KMP算法-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:12
数据结构 邓俊辉
§11.3 KMP算法 11.3.1 构思 上一节的分析表明，蛮力算法在最坏情况下所需时间为主串长度与模式串长度的乘积， 无法应用于规模稍大的应用环境，故很有必要改进。为此，不妨从分析以上最坏情况入手。 稍加观察不难发现，之所以需要大量的时间，是因为存在大量的局部匹配：每一轮的m 次比对中，仅最后一次可能失配。另外，一旦发现失配，主串、模式串的字符指针都要回退， 并从头开始下一轮尝试。 实际上，绝大部分这类字符比对操作都不必要，因为对于主串内在前一轮迭代中已经接 受过比对且比对成功的字符，我们已经掌握了它们的所有信息。只要充分利用这些信息，应 该可以大大提高匹配算法的效率。 以下以蛮力算法的前一版本（代码11.1）为基础进行改进。 简单示例 如图11.4，用T[i]和P[j]分别表示当前正在接受比对的一对字符。 图11.4 刟用以往癿成功比对所提供癿信息，可以避 免主串字符指针癿回退 图11.5 刟用以往癿成功比对所提供癿信 息，有可能使模式串大跨度地右秱 当本轮比对进行到最后一对字符并发现失配后，蛮力算法会令两个字符指针同步回退 （i = i-j+1和j = 0），然后从这一位置继续比对。然而事实上，指针i完全不必回退。 经前一轮比对我们已经清楚地知道，主串的子串substr(T, i-j, j)完全由'0'组成。因此， 在回退之后紧接下来的一轮迭代中，前j-1次比对将注定会匹配。既然如此，尽可让i保持 不变并且令j = j-1，然后继续比对。请注意，如此将使下一轮比对减少j-1次！ 上述“i保持不变并且令j = j-1”的含义，可理解为“将P相对于T向右移动一个单元， 然后从前一失配位置继续比对”。实际上这一技巧可推而广之，利用以往的成功比对所提供 的信息，不仅可避免主串字符指针的回退，而且可使模式串尽可能大跨度地右移。 一般实例 如图11.5所示，再来考查一个更具一般性的实例。 本轮比对进行到发现'E' = T[i] P[4] = 'O'失配后，在保持i不变的同时应将模 式串P右移几个单元呢？有必要逐个单元地右移吗？不难看出，在这一情况下移动一个或两 个单元都是徒劳的。事实上，根据此前的比对结果，必然有 suffix(prefix(T, i), 4) = substr(T, i-4, 4) = prefix(P, 4) = "REGR" 若在此局部能够实现匹配，则至少紧邻于T[i]左侧的若干字符均应得到匹配比如， 当P[0]与T[i-1]对齐时，即属这种情况。注意到i-1是能够如此匹配的最左侧位置，故可放 心地将P右移4-1 = 3个单元（等效于i保持不变，同时令j = 1），然后继续比对。