一、问题描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

二、解题思路

有一个黑科技 String.indexOf()这一个函数可以直接解决这道题，时间还是100%，不过不知道能不能直接调用这个API，如果不使用这个API的话就要用KMP算法，对于KMP算法有一篇博客写的非常好，今天上午手写KMP出现了问题看了这篇博客恍然大明白。

KMP算法解析

三、代码

调用api：

class Solution{public int strStr(String haystack,String needle){return haystack.indexOf(needle);}
}

使用KMP算法：

class Solution {public int strStr(String haystack, String needle) {if(needle==null||needle.equals(""))return 0;if(haystack==null||haystack.equals(""))return -1;char[] h=haystack.toCharArray();char[] n=needle.toCharArray();int[] next=getNext(n);int i=0;//遍历haystack的指针int j=0;//遍历needle的指针while(i<h.length&&j<n.length){char cur=n[j];if(h[i]==cur){i++;j++;}else if(j==0)i++;else{j=next[j];}}return (j==n.length?i-j:-1);}public int[] getNext(char[] c){int[] next=new int[c.length];next[0]=-1;if(next.length>1)next[1]=0;for(int i=2;i<c.length;i++){if(c[i-1]==c[next[i-1]]){next[i]=next[i-1]+1;}else{int index=i;while(index>1) {int k = next[index - 1];int temp = next[k];if (temp != -1 && c[i-1] == c[temp]) {next[i] = next[k] + 1;break;}index = temp;}if(index<=1)next[i]=0;}}return next;}
}

四、结果

第一种方式100%

第二种方式我进行使用charArray进行优化后还是没能效率很高，不过也还ok吧。

执行时间	3ms	41.05%
消耗内存	39.8M	5.43%

五、总结

对于KMP算法要做几点说明：

1）这里的next数组表示next[i]:在第i位之前的子字符串的最长公共前缀后缀。

2）是用动态规划思想求解next时，如果next[i-1]!=str.charAt(next[i-1])时不能直接将next[i]设置成0，因为最长公共前缀后缀可能会缩短，但不为0.如：

AABAAAC 已知前6位next数值分别为-1，0，1，0，1，2，由于第6位的字符A和next[5]=2位的字符B不匹配，但是公共前缀长度为2不是0，因此要进行递归计算，可以用一个while循环代替。

3）KMP算法其实不难，难的是很少有人能够将它描述清楚，要经常思考总结代码。