217      阿里云  技术社区[云栖]

KMP字符串匹配

KMP字符串匹配

设文本为字符串T，长度为n；模板为字符串P，长度为m；并有n>=m。

KMP算法的复杂度为O（m+n），O（m）为模板预处理时间，O（n）为查找匹配所用时间。

传统的暴力匹配未能利用已匹配部分的信息，效率低下。

KMP的核心在于构造状态转换图，可用失配函数表示。

对比见下图。

最后更新：2017-04-03 07:56:55

  上一篇： 用snmp4j开发网管应用(一) - SNMP

  下一篇： 银行离开IBM必死？国货10年内无法接盘