1.字符串查找(kmp)
来源:
lintcode-字符串查找
lintcode-字符串查找II
问题描述
描述
对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1。
说明
在面试中我是否需要实现KMP算法?
不需要,当这种问题出现在面试中时,面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。
样例
如果 source = “source” 和 target = “target”,返回 -1。
如果 source = “abcdabcdefg” 和 target = “bcd”,返回 1。
挑战
O(n2)的算法是可以接受的。如果你能用O(n)的算法做出来那更加好。(提示:KMP)
解决思路
题目说明中提示了此题的目的为考察KMP算法,但是并不要求强行实现,那么本文将作出两种实验方式,即O(N)和O(N2)两种方法,另外,在文后会有自己对KMP算法的一些理解。
1.暴躁(cao)老哥型方法
当然就是穷举了,假设两个字符串为
1 | ACBACDBB ------T串 |
那么我们可以首先比较T[0]和P[0],如果相等则比较T[1]和P[1],如果一直到p串结束都相等则返回,中间如果有不相等,则比较T[1]和P[0]…..
即:逐个比较,当发生不相等时,将T串的开始比较位置向后移动一位,再次逐个比较,直到拿到结果。
这种方法胜在简单粗暴,虽然浪费了点但是能在短时间内理解并实现。
2.机制boy型方法(KMP算法)。
在上面的例子中,当第一次发现AC相同但是B/D不同时,再见将T[1]和P[0]相比较,是一个浪费的行为,因为因为很明显:前面的2位都与自身的前两位一样,而自身的前两位并无相等,可以推出T[1]和P[0]肯定不相等。
这就得出KMP的基本思想:将之前一次的比较信息(如前面的AC两位相等)不要抛弃,而是从这个信息中获取我们应该跳过一些“必不可能”匹配的值,以此来提高性能。
重新举例:
1 | BBC ABCDAB ABCDABCDABDE -------T串 |
在这个例子中,
1.第一次比较:T[0] != P[0],向后移一位;
2.第二次比较:T[1] != P[0], 向后移一位;
..
3.直到:T[4] = P[0],都向后移动一位;
4.T[5] = P[1],再次都想后移动一位。
…
1 | BBC ABCDAB ABCDABCDABDE -------T串 |
5.直到:T[10] != P[6],这个时候返回第三部,重新从T[5]和P[0]开始比较吗?no!!此时肉眼可见,机智的方法是将字符串这样比较:
1 | BBC ABCDAB ABCDABCDABDE -------T串 |
即直接比较T[10]和P[2] 空格与C,为什么呢?因为此时前面的2位AB我们是可以知道他们相等的,怎么知道的呢?
注意在 4 步骤后的示例中,P串的前6位已经完全匹配了,想知道在T中刚比较过的有几位与P串开头相同,只需要比较已经匹配的6位中,前缀和后缀相同有几位就好。
在此例中:前6位为ABCDAB
,明显是2位相同(前缀AB和后缀AB),那么只需要将T[10]与P[2]相比较就好。
6.T[10] != P[2],此时前面两位为AB
,前缀与后缀并无相同,所以将T[10]与P[0]进行相比。
7.T[10] != P[0],比较 P[11] 和P[0],进入下一个循环。
8.由于匹配可能在P串的任何一个地方“断裂”,那么每次断裂,都需要算一次“前缀后缀相同的长度”,也是极其浪费的行为,因此,在KMP算法开始前,会对P串进行一次计算,得到在每个位置发生“断裂”时,P串指针回溯的位置,即当前已匹配字段的前缀后缀相同长度。也就是众多KMP算法讲解中的next数组。
总结:原始的暴力方法,当发现不相同后,将T串的指针回溯,这样及其浪费,而在KMP中,避免了T串的指针回溯,在发现不相等时,通过对已匹配字段的分析,将P串指针回溯一个适合的值,而T串指针只有在首字母就不相同时才会继续前进。
写完这一段,深感自己写的糊里糊涂,但是已尽到目前的能力,后续如果有能力,可以再出一个插图版的讲解。
在这里介绍两个我在学习过程中,看到的关于KMP的博客,属于个人认为讲解的较为清晰的,分享给大家,一起进步。
简洁,说明原理型
详细,逻辑鬼才型
个人推荐:先读简洁篇,对原理有个大概的了解,然后去细读详细篇,否则可能会出现完全看不懂的情况。当然,如果你看我的博客就已经懂了(怎么可能!!),烦请一定留言告诉我,鼓励下我!!
实现代码
暴躁老哥版本(O(N2))
1 | public int stringIndex(String source, String target) { |
机制boy型(O(N))
1 | //计算返回值 |
后记
单就字符串查找这个算法而言,网上思路繁多,而且自己多想一下总有具有自己特色的实现方法。
KMP算是一个比较通用且效率较为不错(非最优)的实现方法,思路较为一致:找出一个当匹配失败时子串回溯的长度。然而在具体实现过程中,尤其是next数组的求解过程中,我看到了许多思路且都很难快速理解。
恕在下愚钝,理解了老半天还是模模糊糊的,万一哪天豁然开朗,再来重新补充一份简单易懂的讲解。
完。
ChangeLog
2018-09-15 添加思路及KMP讲解 2018-09-16 添加实现代码以上皆为个人所思所得,如有错误欢迎评论区指正。
欢迎转载,烦请署名并保留原文链接。
更多学习笔记见个人博客——>呼延十