题目：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
- 1 <= haystack.length, needle.length <= $10^4$
- haystack 和 needle 仅由小写英文字符组成
题目来源：力扣（LeetCode）链接
题解：
- 方法一：暴力匹配
class Solution {
public int strStr(String haystack, String needle) {
int l1 = haystack.length();
int l2 = needle.length();
// 如果要找的字符串比被找的字符串长，就直接返回-1
if (l1 < l2) {
return -1;
}
char[] arr = needle.toCharArray();
// 遍历被查找的字符串
for (int i = 0; i < l1; i++) {
int index = 0;
// 如果第一个字符匹配就继续查找，一旦有不匹配的就退出内层循环
for (int j = i; j < i + l2; j++) {
if (haystack.charAt(j) == arr[index]) {
index++;
} else {
break;
}
}
// 内层循环结束，如果 index=l2 说明找到了，此时 i 就是第一个匹配的下标
if (index == l2) {
return i;
}
}
// 如果循环结束，且没有返回，则说明没有找到
return -1;
}
}
- 方法二：KMP 算法 (参考代码随想录里面的讲解点我跳转)
class Solution {
public int strStr(String haystack, String needle) {
// 如果 needle 字符串为 null 或 ""，则直接返回 0
if (needle.length() == 0) {
return 0;
}
// 调用方法得到 needle 的前缀表
int[] next = new int[needle.length()];
getNext(next, needle);
// 指针 j 表示 needle 的下标
int j = 0;
// 遍历字符串 haystack
for (int i = 0; i < haystack.length(); i++) {
// 如果字符不匹配，指针 j 就根据前缀表 next 回退
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = next[j - 1];
}
// 如果字符匹配，那么 i 和 j 同时向后移动
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
// 如果 j 等于字符串 needle 的长度，则说明第一次完全匹配，返回对应的下标
if (j == needle.length()) {
return i - needle.length() + 1;
}
}
// 如果字符串遍历完成后，依然没有返回，则说明没找到
return -1;
}
// 获取 needle 的前缀表
public void getNext (int[] next, String s) {
// j 的初始值对应长度为前 1 个字符的子串的最长相同前后缀
int j = 0;
// 长度为前 1 个字符的子串，最长相同前后缀为 0
next[0] = j;
// 遍历字符串 needle 直接从下标 1 开始
for (int i = 1; i < s.length(); i++) {
// 如果前后缀不相同，那么 j 就要回退，一直到相等时结束
while (j > 0 && s.charAt(j) != s.charAt(i)) {
j = next[j - 1];
}
// 如果前后缀相等，就用 j 记录
if (s.charAt(i) == s.charAt(j)) {
j++;
}
// 把长度为前 i 个字符的子串，最长相同前后缀记录到 next 数组对应的位置
next[i] = j;
}
}
}