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

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

2017-06-19 蓝鸥
438人 浏览:

  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. 广告1
  2. 广告2
  3. 广告3
  4. 广告4