KMP算法(详解加图解)

前言

最近学校对数据结构的串部分KMP算法进行了讲解,出于好奇,感觉这个代码简洁干练,但思想有很我发现KMP算法确实很巧妙,所以在此想做一个总结,分享给大家.子字符串查找问题,历史上有很多种方法,都是在此问题上,提高整体的效率,提炼出一个简洁,时间复杂度较低的算法.这篇博客介绍的KMP算法求解子字符串问题就是由Knuth,Morris,Pratt三位大佬创建出来的.

问题描述

子字符串查找,给定一个长度位N的文本字符串和一个长度为M的模式字符串,在文本中找到和该模式字符串相符的子字符串.求文本文件满足要求的字符串的首元素下标.
文本:a b c a b c a b c f,模式串:c a b c a,你可能一看就知道答案时2,但是当文本字符串足够长,长度达到一万,甚至十万,此时如果还是采用"肉眼观察法",就很难观察的出来,往往黑客盗取密码就是在几万行代码中输入Password关键词找到相应的位置,来达到目的.
说到这里,可能有人会觉得可以采用暴力的方法求解(Brute Force),如下图:
暴力求解通过遍历文本串和模式串,通过指针i和指针j的回溯,来达到找子字符串的目的.其思路主要就是通过遍历文本串中的每一个元素,以此元素为起点,与模式串进行比较,如果相等,就是同时向后移动,但是如果最终出现不匹配的情况,文本串就需要回溯到起始位置的下一个元素继续遍历. 对时间复杂度分析就会发现,最差的情况时间复杂度为O(NM),显然不是最佳的方案.
我们发现暴力算法,每一次与模式串比较,最终文本串都需要回溯一遍,那有没有一种方法可以让文本串中的指针i不进行回溯呢,KMP算法就是如此.

KMP算法思想

以上面的问题为例子,使用KMP算法求解.与暴力求解算法不同的地方是,KMP算法中的指针i不需要