蓝鸥旗下品牌: 鸥课学院
全国咨询电话:010-59418771
大连
您的位置: 首页 > 最新资讯 > 【原创】KMP算法分析与实现

【原创】KMP算法分析与实现

2017-06-22 蓝鸥
645人 浏览:

  KMP算法——KMP(Knuth-Morris-Pratt) 克努特—莫里斯—普拉特 操作

  主要作用:字符串查找算法,常用于大型一个文本字符串中找一个模式字符串的出现文职。此算法由三人于1977年联合发表——Donald  Knuth——唐纳德·克努特,Vaughan Pratt——沃恩·普拉特,James H. Morris——詹姆斯·H·莫里斯

  file0001_副本.png

  我们先看最简单的解决思路:

file0002_副本.png  

  例如:

  file0003.png

file0004.png

  我们说此种算法为暴力匹配算法。

  下面分析一下:

  file0005.png

  发现问题,用KMP算法解决这样的问题。

file0006_副本.png

file0007.png

file0008.png

file0009.png

  KMP关键在next数组的分析和应用:

  file0010.png

file0011.png

  代码如下:

  

  新的问题出现,需要分析和解决。

file0014.png

  优化后的关键代码:

  file0015.png

  此文为KMP算法的展示,很多人都知道KMP算法,也会KMP算法,重点在于想让更多的人知道这一算法,字符串检索算法中最厉害的算法。


  1. Angular2最全首发
  2. 广告
  3. PHP语法基础
  4. JavaScript面向对象

「蓝鸥教育 」 一个做IT行业 「定岗直招」的学校!

就业保障 / 课程学费 / 课程大纲 / 全国校区

立即咨询
稍后联系