你被欺骗了很久：前缀和真前缀

作者：刘毅

https://www.61mon.com/index.php/archives/209/

相信很多读者都看过网上博客对 KMP 算法的讲解，其中必提及的一个名词就是：前缀。那么请问你心中理解的前缀的定义是什么呢？

对于字符串 “china”，其前缀为：

china, chin, chi, ch, c

你的想法是不是和上面一样呢。但是我很遗憾地告诉你，KMP 之前缀不是这样的，它是这样的：

chin, chi, ch, c

难道是我们记错前缀的概念了？不！不是我们记错了，只是有人在指鹿为马而已。下面来揭晓真像吧。

如此看来，KMP 之前缀并非前缀，而是真前缀！而大多数（几乎所有）的博客都在以 “真前缀” 去定义“前缀”。

next 数组是 KMP 的一个核心概念，而真前缀又是 next 数组的核心。算法本属于一个很严谨的领域，这种在重要概念上却还指鹿为马的行为，是应该需要我们注意和避免的。

不知道大家有没有发现，你所看过的 KMP 博文无一提及真前缀的定义，除了阮一峰的字符串匹配的 KMP 算法。

哈哈，阮老师太粗心了，在文章开头阮老师已经讲过，他是阅读了 Jake Boxer 的文章才明白 KMP 的，那原文是什么样的呢？

---

●本文编号536，以后想阅读这篇文章直接输入536即可

●输入m获取文章目录

推荐↓↓↓

 

大数据与人工智能

更多推荐《18个技术类微信公众号》

涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。