Leetcode28. 实现 strStr()（C语言） 题目：
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。例:
输入: haystack = “hello”, needle = “ll”
输出: 2
思路：
kmp算法。分为文本串与模式串，先构造临时数组存储模式串前后缀匹配情况；再用临时数组用模式串依次与文本串匹配。
避免暴力法中每次遇到不匹配时从头匹配
阿三哥讲的超清晰的kmp算法
【Leetcode28. 实现 strStr()（C语言）】代码：
void kmp_init(const char *s, int *tmp, int size) { //临时数组存储字串前后缀匹配情况
tmp[0] = 0;
for (int i = 1;
i < size;
i++) {
if (s[i] == s[tmp[i - 1]])tmp[i] = tmp[i - 1] + 1;
else {
int j = i - 1;
while (tmp[j] > 0 && s[tmp[j]] != s[i])j = tmp[j] - 1;
//找到上一个出现s[i]的位置if (tmp[j] > 0)tmp[i] = tmp[j] + 1;
//从上一次出现位置为起始，开始匹配
elsetmp[i] = (s[i] == s[0]);
//从tmp0开始匹配，不匹配为0
}
}
}int strStr(const char *src, const char *dest) {
if (!dest || !src)return -1;
if (!*dest) return 0;
int size = strlen(dest);
int *tmp = malloc(sizeof(int) * size);
kmp_init(dest, tmp, size);
int i, j;
for (i = j = 0;
src[i] && j < size;
i++) {//每次文本串指针均后移
if (dest[j] == src[i])j++;
//匹配，模式串指针后移
else if (j) {//至少一个匹配
while (tmp[j - 1] > 0 && dest[tmp[j - 1]] != src[i])j = tmp[j - 1];
//模式串定位到上一个匹配位置if (tmp[j - 1] > 0)j = tmp[j - 1] + 1;
//模式串定位到匹配位置（不为起始位置）
elsej = (dest[0] == src[i]);
//模式串从头和src[i]比较，若不同，下一循环仍从头比较
}
}free(tmp);
if (j < size)return -1;
//模式串不能完全匹配
return i - size;
//返回第一次出现位置
}
//参考评论区@swhc
