算法：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算法吧，等弄明白了单独写一篇。