主题描述
实现（）函数。
给定一个字符串和一个字符串时间复杂度空间复杂度C++代码算法(KMP)$O(nm)
<p>
，找出字符串中出现该字符串的第一个位置（从 0 开始）。如果不存在则返回 -1。</p>
样本
输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1
阐明
当它是一个空字符串时java字符串匹配度算法，我们应该返回什么值？这是面试时问的好问题。
对于这个问题，当它是一个空字符串时，我们应该返回 0。这与 C 中 () 和 Java 中 () 的定义相匹配。
算法1（暴力枚举）$O(nm)$ 直接根据定义java字符串匹配度算法，暴力匹配每个位置的子串。时间复杂度 C++ 代码
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i < n - m + 1; i++) {
bool ok = true;
for (int j = 0; j < m; j++)
if (haystack[i + j] != needle[j]) {
ok = false;
break;
}
if (ok)
return i;
}
return -1;
}
};
算法 2（KMP 算法）$O(n+m)$ 创建下一个模式字符串数组，这是当前不匹配后可以比较的下一个位置。将下一个数组应用于要匹配的字符串。时间复杂度空间复杂度C++代码
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.length(), m = needle.length();
if (m == 0)
return 0;
vector next(m);
next[0] = -1;
int j = -1;
for (int i = 1; i < m; i++) {
while (j > -1 && needle[i] != needle[j + 1]) j = next[j];
if (needle[i] == needle[j + 1]) j++;
next[i] = j;
}
j = -1;
for (int i = 0; i < n; i++) {
while (j > -1 && haystack[i] != needle[j + 1]) j = next[j];
if (haystack[i] == needle[j + 1]) j++;
if (j == m - 1)
return i - m + 1;
}
return -1;
}
};