免费的招聘网站有哪些,厦门网站设计公司找哪家,大连牛人网络推广有限公司,天猫seo搜索优化title: 代码随想录Day9 date: 2024-01-04 19:38:32
代码随想录笔记 categories:技术 代码随想录day9-KMP算法|28. 找出字符串中第一个匹配项的下标
宏观
本来使用暴力 O(m*n)的算法#xff0c;通过KMP方法#xff0c;基于前缀表构建失败函数next数组#xff0c;在失败后进…
title: 代码随想录Day9 date: 2024-01-04 19:38:32
代码随想录笔记 categories:技术 代码随想录day9-KMP算法|28. 找出字符串中第一个匹配项的下标
宏观
本来使用暴力 O(m*n)的算法通过KMP方法基于前缀表构建失败函数next数组在失败后进行回退只退模式串指针有效降低了时间复杂度
next数组实现
std::vectorint build_next(const std::string pattern) {int n pattern.length();std::vectorint next(n, 0);int j -1;next[0] j;for (int i 1; i n; i) {// 当前缀和后缀不同向前回溯while (j 0 pattern[i] ! pattern[j 1]) {j next[j];}// 当前缀和后缀相同if (pattern[i] pattern[j 1]) {j;}next[i] j;}return next;
}主函数实现
std::vectorint kmp_search(const std::string text, const std::string pattern) {std::vectorint positions; // 存储匹配的起始位置std::vectorint next build_next(pattern);int j -1;for (int i 0; i text.length(); i) {// 当前字符不匹配根据next数组回溯模式字符串的指针while (j 0 text[i] ! pattern[j 1]) {j next[j];}// 当前字符匹配if (text[i] pattern[j 1]) {j;}// 完全匹配模式字符串if (j pattern.length() - 1) {positions.push_back(i - j);j next[j]; // 继续搜索下一个匹配}}return positions;
}
例题1-28.
class Solution {
public://构造 next 数组void getNext(int* next, const string s){int j -1;next[0] j;for(int i 1; i s.size(); i) {while (j 0 s[i] ! s[j 1]) {j next[j]; }if (s[i] s[j 1]) { j;}next[i] j; }
}int strStr(string haystack, string needle) {//KMP算法if (needle.size() 0) {return 0;}int next[needle.size()];getNext(next, needle);int j -1; // // 因为next数组里记录的起始位置为-1for (int i 0; i haystack.size(); i) { // 注意i就从0开始while(j 0 haystack[i] ! needle[j 1]) { // 不匹配j next[j]; // j 寻找之前匹配的位置}if (haystack[i] needle[j 1]) { // 匹配j和i同时向后移动j; // i的增加在for循环里}if (j (needle.size() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.size() 1);}}return -1;}
};总结
对于next数组的理解还不够深入还不能做到自己完整手撸代码本周六专门花一天时间突破一下这几天遇到的重难点
