给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
#include <iostream>
#include <string>using namespace std;int strStr(string haystack, string needle) {int h_len = haystack.length();int n_len = needle.length();if (n_len == 0) return 0; // 空needle字符串,返回0for (int i = 0; i <= h_len - n_len; ++i) {int j;for (j = 0; j < n_len; ++j) {if (haystack[i + j] != needle[j]) break; // 检查当前位置开始的子串是否与needle匹配}if (j == n_len) return i; // 如果完全匹配,返回下标i}return -1; // 没有匹配项,返回-1
}int main() {string haystack = "hello";string needle = "ll";int result = strStr(haystack, needle);cout << "匹配项的下标为:" << result << endl;return 0;
}
时间复杂度分析:
时间复杂度是O((n-m+1)*m),其中n是haystack字符串的长度,m是needle字符串的长度。在主循环中,我们最多进行了(n-m+1)次迭代,每次迭代需要检查needle的长度m个字符与haystack中的子串是否匹配。因此,总的时间复杂度为O((n-m+1)*m)。
空间复杂度分析:
空间复杂度是O(1),因为算法中只使用了常数个额外变量,与输入字符串的长度无关。