数据结构（邓俊辉）学习条记】串 08——KMP算法：再改进

1. 美中不敷

以上，我们不但给出了 KMP 算法，同时也证实它的时间复杂度已经到达了渐进意义上的最优，也就是最坏情况也不凌驾 O(n)。而该算法现在这个版本也绝非美满无缺，接下来我们就会看到在某一方面它依然存在一个渺小的瑕疵。要针对这一缺陷，对它再做改进。
为了显现此中仍然存在的题目，我们从如许一个反例入手。

  

• 起首确认对于如许一个模式串，这里给出的简直是他的 next 查询表。与全部情况一样，KMP 算法起首将文本串与模式串在首字符位置对齐，并启动第一轮的字符比对。
  不能看出在颠末3次乐成的比对之后，算法将初次适配于这一位 1-0 字符。
    
  
• 于是根据算法的流程，接下来我们应该将模式串中的这个字符，更换为它对应的 next 表项所指的谁人字符，也就是2号字符。因此接下来等效于将模式串向右侧滑动一个单位，从而按照 next 表的语义，将2号字符与刚才失配的谁人文本串字符对齐，并再做一次比对。
    
  
• 城然，这次比对依然会失败。因此接下来我们将去查询2号字符在 next 表中所对应的那一项，也就是1。从结果上看，这仍然等价于将模式串再向右滑动一个单位，从而以1号字符，与文本串中失配的这个字符再次对齐，并再做一次比对。
    
  
• 同样不丢脸出，这次比对也会以失败返回。因此我们又会继而去查询这个字符，也就是这个字符所对应的 next 表象。并按照这个体现的指示，将0号字符，也就是首字符，与文本串中刚才失配的谁人字符对齐，并随即做一次字符的比对。
    
  
• 再一次的，这次比对依然会以失败返回。于是根据算法的逻辑，我们将去查询这个字符，也就是首字符在 next 表中所对应的表象。从而将假想存在的谁人通配哨兵与文本串中失配的字符对齐。
    
  
• 固然，既然是通配符，这次比对也必
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金