KMP算法细节详解(带动图理解)(1)
前言
KMP算法是为了字符串匹配问题而被研究出来的,字符串匹配问题就是查看一个字符串A是否是字符串B的子串,如果是字串的话,在B的哪个位置?此算法代码简练,但理解起来非常困难,建议挑出一整块时间来专门学习,本文作者写的非常用心,还不了解KMP的小伙伴一定要静下心来慢慢细品,你一定会有所收获🍊
一、字符串匹配问题
如果遇到这种在一个字符串中寻找另一个字符串的子串这种问题,大多数人第一时间想到的肯定是通过暴力匹配算法来完成,也就是Brute-Force算法简称BF算法,时间复杂度为O(m*n),如果有上千行上万文本呢?,时间成本一定会很高,所以D.E.Knuth,J.H.Morris和V.R.