给定一个 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() 定义相符。
题解1(直接使用java的indexOf()方法,难道它不香吗？)
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :38.3 MB, 在所有 Java 提交中击败了5.04%的用户
题解2(在题解区有一个大神给出了详细的KMP算法解析)
暴力破解法
// 伪代码
public int strStr(String haystack, String needle) {
int M = needle.length();
int N = haystack.length();
for (int i = 0; i < N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (needle.charAt(j) != haystack.charAt(i+j))
break;
}
// 匹配成功
if (j == M) return i;
}
return -1;
}
对于暴力算法，如果出现不匹配字符，同时回退 haystack 和 needle 的指针，嵌套 for 循环，时间复杂度 O(MN)，空间复杂度O(1)。最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。
KMP算法
KMP 算法的不同之处在于，它会花费空间来记录一些信息。KMP 算法永不回退 haystack 的指针 ，不走回头路（不会重复扫描 haystack），而是借助 dp 数组中储存的信息把 needle 移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间。
KMP 算法的难点在于，如何计算 dp 数组中的信息？如何根据这些信息正确地移动 needle 的指针？这个就需要确定有限状态自动机来辅助了，别怕这种高大上的文学词汇，其实和动态规划的 dp 数组如出一辙，等你学会了也可以拿这个词去吓唬别人。
还有一点需要明确的是：计算这个 dp 数组，只和 needle 串有关。意思是说，只要给我个 needle，我就能通过这个模式串计算出 dp 数组，然后你可以给我不同的 haystack，我都不怕，利用这个 dp 数组我都能在 O(N) 时间完成字符串匹配。
明白了 dp 数组只和 needle 有关，那么我们这样设计 KMP 算法就会比较漂亮：
public class KMP {
private int[][] dp;
private String needle;
public KMP(String pat) {
this.needle = needle;
// 通过 needle 构建 dp 数组
// 需要 O(M) 时间
}
public int search(String haystack) {
// 借助 dp 数组去匹配 haystack
// 需要 O(N) 时间
}
}
这样，当我们需要用同一 needle 去匹配不同 haystack 时，就不需要浪费时间构造 dp 数组了。
更详细的原文解析请见原文KMP算法
