给你两个字符串 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 。
- 暴力解法
- KMP算法
一：暴力解法，在字符串很长时可能超时。
int strLen(char*);
int strStr(char* haystack, char* needle) {
int i, j;
for (i = 0; i < strLen(haystack); i++) {
if (haystack[i] == needle[0]) {
for (j = 0; j < strLen(needle); j++) {
if (haystack[i + j] != needle[j]) {
break;
}
}
if (j == strLen(needle)) {
return i;
}
}
}
return -1;
}
int strLen(char* str) {
int i = 0;
while (str[i] != '\\0') {
i++;
}
return i;
}
二：KMP算法：
#include <stdlib.h>
int strStr(char* haystack, char* needle) {
// 处理空 needle 的情况
if (needle[0] == '\\0') return 0;
int n = 0, m = 0;
// 计算 needle 和 haystack 的长度
while (haystack[n] != '\\0') n++;
while (needle[m] != '\\0') m++;
// needle 比 haystack 长，不可能匹配
if (m > n) return – 1;
// 构建 KMP 算法的部分匹配表（next数组）
int* next = (int*)malloc(m * sizeof(int));
if (next == NULL) return – 1; // 内存分配失败
// 构建 next 数组
next[0] = 0;
for (int i = 1, len = 0; i < m;) {
if (needle[i] == needle[len]) {
len++;
next[i] = len;
i++;
} else {
if (len != 0) {
len = next[len – 1];
} else {
next[i] = 0;
i++;
}
}
}
// 使用 KMP 算法进行匹配
int i = 0, j = 0;
while (i < n) {
if (haystack[i] == needle[j]) {
i++;
j++;
}
if (j == m) {
free(next);
return i – j; // 匹配成功，返回起始位置
} else if (i < n && haystack[i] != needle[j]) {
if (j != 0) {
j = next[j – 1];
} else {
i++;
}
}
}
free(next);
return -1; // 未找到匹配
}
