前缀和真前缀的区别分析

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

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

china, chin, chi, ch, c

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

chin, chi, ch, c

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

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

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

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

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