怎么做地下彩票网站,wordpress模板开发,做推广网站那里好,自助服务系统网站思路#xff1a;
朴素匹配有很多步骤是多余的
KMP算法能够避免重复匹配
KMP算法主要是根据子串生成的next数组作为回退的依据#xff0c;它记录了模式串与主串(文本串)不匹配的时候#xff0c;模式串应该从哪里开始重新匹配。
这里讲一下为什么用模式串的最大公共前后缀…思路
朴素匹配有很多步骤是多余的
KMP算法能够避免重复匹配
KMP算法主要是根据子串生成的next数组作为回退的依据它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
这里讲一下为什么用模式串的最大公共前后缀求解NEXT数组参考B站木子喵NEKO的视频【【neko算法课】KMP算法【7期】】 https://www.bilibili.com/video/BV1234y1y7pm/?share_sourcecopy_webvd_source5fc45b3a16cefaa9c36d42d5626cd9e6 用例子思考时我们可以肉眼看到需要移动的位置是根据B向后移动几个可以最大化的对齐A(在i之前意味着找到i前面文本子串(A)与模式子串(B)中重合的部分。
既然i前面都是重合因为i这里发生了不匹配前面都匹配直白说就是一样的那就不用看文本串了直接看模式串前后是否有重合的部分也就是看模式串的最大公共前后缀。如果没看懂可以往下看。 kmp整体上分两步
1计算前缀表
2根据前缀表移动两个指针进行匹配 1计算前缀表就是求解文本串指针回退的位置
ps:文本串用i指针模式串用j指针
以下分别用A,B代指文本串与模式串。
A串中i指针前面第一次循环时AB发生不匹配的位置前用A子串与B子串代称。
当A,B遇到不匹配的字符时j指针回退回退依据是当前不匹配位置前一位最大前后缀的长度
为什么呢通俗的说就是不匹配了看前面有哪些已经最大化的匹配上了不匹配位置前一位的next值代表了B自身前后一致的最大长度根据前面讲的A子串等效B子串也就代表了AB子串前后一致的最大长度也就代表了A子串的后面与B子串的前面一致的最大长度也就是B需要向后移动几个字符而j指针的移动代表着B向后移动也就是j指针要移动到的位置。
j回退到上次最大化匹配的位置
如果还不匹配再次查看不匹配位置前一位next的值。
如果匹配j加一也就意味着j向后移动一位i向后移动写在了for循环里。
同时每次更新next[i]
void getNext(string s,vectorint next)
{int j 0;next[0] 0;for(int i 1;is.size();i){while(j0 s[i] ! s[j]) j next[j-1];if(s[i] s[j]) j;next[i] j;}
}
2 模拟匹配过程
如果不匹配按着next数组回退j指针如果匹配J增一
最后如果j指向了模式串的末尾说明找到了完整匹配返回匹配的起始下标
如果没找到返回-1
int strStr(string s,string t)
{if(t.size()0) return 0;//这里需要初始化next数组这里用址传递传参给getNext函数vectorint next(t.size());getNext(t,next);int j 0;for(int i 0;is.size();i){
//若果遇到s,t不匹配按着next表回退while(j0 s[i]!t[j]) j next[j-1];if(s[i] t[j]) j;
//如果j指向t的最后一位说明前面均匹配成功那么返回的第一个匹配项是当前i位置减去已经匹配的t的长度再加一if(j t.size()) return (i - t.size()1);}return -1;
}
注修改了一处传参遇到的问题涉及值传递、指针传递与地址传递的比较可以略过。
void getNext(string s,vectorint next) vectorint next(t.size()); getNext(t,next);
这里string s是值传递也可以用地址传递
vectorint next,必须用地址传递这样好处相比于值传递与指针传递有三点
1避免不必要的拷贝调用函数时不用创建next的副本不会导致额外的时间内存开销
2保持函数接口整洁引用传递可以直接修改传入的对象不需要显示的管理内存。
3避免空指针问题指针传递需要检查指针是否为空否则运行错误引用传递无需担心因为引用会绑定到有效的对象。
因此地址传递是c中处理复杂参数中常见于推荐的方法。
