学习
实践
活动
工具
TVP
写文章

算法:13.Implement strStr

https://www.lintcode.com/problem/word-search/description

描述

对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 。

样例

如果 source =  和 target = ,返回 。

如果 source =  和 target = ,返回 。

挑战

O(n2)的算法是可以接受的。如果你能用O(n)的算法做出来那更加好。(提示:KMP)

思路

对于Java来说,String类有indexOf方法。O(n^2)的实现是很容易想到的,逐个字符对比,从source的第一个字符开始,如果发现不匹配,就将匹配位置加一,再重新匹配。

代码

记得是有个更高效的匹配算法的,当target字符串的内部重复字母越多时效率越高。但具体做法已经忘记了。

查了一下更优的算法叫KMP算法。看了下大概介绍,简单实现了一个版本。KMP算法是会针对target字符串建立一个数组,在匹配失败时根据数组中对应的元素值计算下次比较时target参与比较的字符索引。

根据这个想法,自行实现的算法如下,也是根据target建立一个数组,数组中的元素值是target中对应位置的字符匹配失败时,source中比较索引移动的位置:

最后看看KMP实现的查找算法:

小结

KMP算法是很著名和经典的一个算法。next的实现不是那么容易看懂,代码需要仔细思考。

第二版自己实现的比第一版的效率有改进,但是改进程度比较小,在最好的情况下与第一版的遍历比较是相同的效率,都是需要n+m次比较,最差的情况好于遍历比较版本的n*m。

在没有重复字符的情况下,KMP算法反而要低效一些,比如在 "abncddfaoweriupqwer913ljadflweri987" 查找 "ri987" ,KMP反而效率更低些,因为多了回退的操作。

根据测试,在 "abncddfaoweriupqwer913ljadflweri987" (长度35)查找 "ri987" (长度5),三种方法的比较次数分别是:39,39,64.

需要单独写一篇KMP算法,比KMP更好一点的算法也有,叫BM算法吧,等弄明白了单独写一篇。

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

扫码关注腾讯云开发者

领取腾讯云代金券