模式匹配BF算法和KMP算法
我清晰的记得我们学校老师编的数据结构的教材上第一张就是时间复杂度和空间复杂度，然后最经典的就是拿模式匹配BF算法和KMP算法来讲解。当时BF我们亲切的称“Boy Friend”, KMP亲切的称“看毛片”，显得数据结构是如此的通俗易懂，平易近人。而其实，BF是Brute Force，暴力破解的意思，是指用穷举法，举出所有可能的结果，然后逐一检验是否正确的。而在字符串模式匹配中的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。其实也就是一个个字母比较下去，直到得出结果。所以这是最直接也是最暴力的方法，但是耗时是最长的，因为如果字符串很长，你都不知道什么时候能暴力完成。正如破解路由器wifi密码一样，你知道它就是键盘上的字符组合，但是有那么多组合，你一个个试下去肯定能试出来，但是这个过程很漫长很无趣。时间复杂度为O(M*N)。
KMP算法英文简称就不说了，是一个人名。如在匹配的过程中发现正在比较的两个字符不同（称之为失配），那么朴素的算法会将模版串右移一位，重新比较。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。这个还不好讲原理，具体可以看看附加的视频。
文档来源：51CTO技术博客https://blog.51cto.com/u_8697137/3035855
页:
[1]