前綴和真前綴的區(qū)別分析

相信很多讀者都看過網(wǎng)上博客對(duì) KMP 算法的講解，其中必提及的一個(gè)名詞就是：前綴。那么請(qǐng)問你心中理解的前綴的定義是什么呢？

對(duì)于字符串 “china”，其前綴為：

china, chin, chi, ch, c

你的想法是不是和上面一樣呢。但是我很遺憾地告訴你，KMP 之前綴不是這樣的，它是這樣的：

chin, chi, ch, c

難道是我們記錯(cuò)前綴的概念了？不！不是我們記錯(cuò)了，只是有人在指鹿為馬而已。下面來揭曉真像吧。

如此看來，KMP 之前綴并非前綴，而是真前綴！而大多數(shù)（幾乎所有）的博客都在以 “真前綴” 去定義“前綴”。

next 數(shù)組是 KMP 的一個(gè)核心概念，而真前綴又是 next 數(shù)組的核心。算法本屬于一個(gè)很嚴(yán)謹(jǐn)?shù)念I(lǐng)域，這種在重要概念上卻還指鹿為馬的行為，是應(yīng)該需要我們注意和避免的。

不知道大家有沒有發(fā)現(xiàn)，你所看過的 KMP 博文無一提及真前綴的定義，除了阮一峰的字符串匹配的 KMP 算法。

哈哈，阮老師太粗心了，在文章開頭阮老師已經(jīng)講過，他是閱讀了 Jake Boxer 的文章才明白 KMP 的，那原文是什么樣的呢？