首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

作者:刘毅

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、数据库、运维等。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20171214B078SG00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券