古代科举放榜，一群秀才伸长脖子，在榜文上一行行去找自己的名字，既紧张又兴奋，耗时也长，就很累。
也是古代勾决犯人，犯人在处斩名单上一行行找自己的名字，既紧张又兴奋，耗时也长，就很累。
所以，计算机出现后，在一大长串文本中，找一个固定的字符串，就是个当务之急。就跟厨房里的锅一样，必备啊。
ZCBDAPHDEHALCJSUYTREDCGILOVEYOUHJKJGFDEQSDGJKLLJHGFDCVBBNMOOIUYTREDFH
从上面这一串文本中，怎么最快找出I LOVE YOU，就是字符查找算法。
主流的算法有四种，第一种叫暴力查找，听起来很黄，很暴力，其实是笨蛋的方法。
就是一个个对照：Z 不是 I，那就下一个 C。暴力查找，既紧张又兴奋，耗时也长，就很累。
第二种呢，叫 Knuth–Morris–Pratt 算法，缩写叫 KMP 算法，三个计算机科学家搞出来的。
KMP 的原理我不解释了，忒复杂。 笔者曾经耗时 3 小时，才搞清楚那原理和代码（配合战术后仰姿态），当时拍案叫绝，浮了一大白。但让笔者讲明白这玩意，那只能投降。
KMP 大致原理是这样的，如果你名叫：
尼古拉斯亚历山大尼古拉斯凯奇，而榜单是这样的：
尼古拉斯亚历山大尼古拉斯赵四刘能广坤大脚大拿，那么你发现“凯奇” 和 “赵四” 对不上，就不用急着往下挪一位，而是分析“尼古拉斯亚历山大尼古拉斯” 的前缀和后缀，直接往前挪 9 位。
爱懂不懂吧，太费劲了。至于 Next 函数的设计，更是用煤气灶炖猪头 - 烧脑。
说说科学家吧。 Donald Knuth 是大神级的，图灵奖获得者，他的中文名叫高德纳，这个中文名啊，有渊源，是姚期智老师的太太储枫给起的。高德纳最知名的，就属他那煌煌巨著 “计算机编程艺术”。
另一位 Vaughan Pratt 是 Donald Knuth 的学生。再一位是 James H. Morris，这位是卡内基梅隆大学的院长。KMP 是 Morris 和 Knuth 分别提出，之后呢，Pratt 和 Morris 合作写了个报告，最后 1977 年三人联手，发表了 KMP 论文。其中到底三人关系如何，不得而知，有些诡异。
再一个算法是 BM 算法，Boyer–Moore 算法，这个算法更是巧妙。例如：
尼古拉斯亚历山大尼古拉斯凯奇
尼古拉斯亚历山大尼古拉斯赵四刘能广坤大脚大拿
暴力法和 KMP 都是从 “尼” 字开始对比，而 BM 算法则从 “奇” 字开始对比，“奇” 与 “四” 不对，那好，从目标文本后面找，看有没有奇字，有，就直接挪过去。
当时，我就灌了一壶，这比 KMP 更显巧妙。
Robert S. Boyer 是得克萨斯大学的教授。J Strother Moore 一样，也是得克萨斯的。二人还一起开发了一个 LISP 变种， ACL2。
第三个算法是 Rabin-Karp 算法，Richard M. Karp 与 Michael O. Rabin 发明，这二位都是图灵奖获得者。Michael O. Rabin 迈克尔拉宾，提出了非确定自动机的概念，还设计了个拉宾非对称密码。Richard M. Karp 理查德·卡普则是伯克利大学教授，他在空间搜索上发明了分支限界法。
RK 算法有点怪，是将模式字符串计算出哈希值，然后将目标文本字符串中位数相等的所有可能字符串，都计算出哈希值来。然后，将模式字符出的哈希值，与目标文本的所有可能字符串的哈希值一一比较。
这不是更慢吗？
但凡有点脑子的，都会马上想到。
两位图灵奖获得者岂能那么浅薄，关键人家在计算目标文本字符串时，用上了更方便的哈希运算方法。 位数等于模式字符串的所有可能字符串，必然是一位位的往后挪，于是后一个字符串的哈希值，就可以通过前一个字符串的哈希值计算出来。这是精髓所在。
有了这些快速字符超找算法，秀才们再也不必既紧张又兴奋，耗时也长，就很累了。犯人们再也不必既紧张又兴奋，耗时也长，就很累了。
秀才一眼就可以看到自己没中进士，犯人一眼就可以看到午后就要处斩自己。多方便，多踏实啊。
网友评论