79、【字符串】leetcode ——28. 找出字符串中第一个匹配项的下标(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:28. 找出字符串中第一个匹配项的下标
KMP理论及实现
next不减方式构造
class Solution {
public:
void getNext(int next[], string &needle, int m) {
next[0] = 0;
for(int i = 1, j = 0; i < m; i++) {
while(j > 0 && needle[i] != needle[j]) j = next[j - 1];
if(needle[i] == needle[j]) j++;
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if(needle.size() == 0 || haystack.size() == 0) return -1;
int n = haystack.size(), m = needle.size();
int next[m];
getNext(next, needle, m);
for(int i = 0, j = 0; i < n; i++) {
while(j > 0 && haystack[i] != needle[j]) j = next[j - 1];
if(haystack[i] == needle[j]) j++;
if(j == m) {
return i - j + 1; // 因为j的范围为0~m-1,因此需要返回的是i - (j - 1)
}
}
return -1;
}
};
时间复杂度
O
(
n
+
m
)
O(n + m)
O(n+m)
空间复杂度
(
m
)
(m)
(m)
参考文章:28. 实现 strStr()
相关文章
- C/C++ 进程的探索(fork函数)
- C++静态代码分析PreFast
- 【C/C++】排序算法
- 后台开发:核心技术与应用实践1.1 第一个C++程序
- c++中UDP通信实现
- 《像计算机科学家一样思考C++》——第1章 编程方式
- 《好学的C++程序设计》导读
- 【C++】AVL树,平衡二叉树详细解析
- 基于C++面向对象实现(控制台)宠物小精灵对战系统【100010120】
- 理清gcc、libc、libstdc++的关系(libstdc++是gcc搞的,libc++是llvm搞的,他们都是C++标准库的实现)
- 180、【动态规划】leetcode ——583. 两个字符串的删除操作:两种动态规划思路(C++版本)
- 176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)
- 147、【动态规划】leetcode ——62. 不同路径:递归法+迭代法(C++版本)
- 145、【动态规划】leetcode ——70. 爬楼梯:暴力法+动态规划(C++版本)
- 133、【贪心算法】leetcode ——1005. K 次取反后最大化的数组和(模拟变化+贪心策略)(C++版本)
- 96、【树与二叉树】leetcode ——404. 左叶子之和:递归法[先序+后序]+迭代法[先序+层次](C++版本)
- 77、【字符串】leetcode ——151. 反转字符串中的单词(C++版本)
- 70、【哈希表】leetcode——1. 两数之和(C++版本)
- 64、【链表】leetcode——203. 移除链表元素(C++版本)
- C++模板中的静态
- 要写出优雅的二分查找实属不易(C++,LeetCode34)