网站主机注册,住宅和城乡建设部网站,百度做网站推广怎么样,东莞路桥投资建设公司招聘KMP 算法——快速的从主串中找到模式串
当出现字符串不匹配时#xff0c;可以知道一部分之前已经匹配的文本内容#xff0c;可以利用这些信息避免从头再去做匹配了。
KMP 算法 比较指针不回溯#xff0c;仅仅是后移模式串。
每次不匹配的时候#xff0c;找之前已匹配部分…KMP 算法——快速的从主串中找到模式串
当出现字符串不匹配时可以知道一部分之前已经匹配的文本内容可以利用这些信息避免从头再去做匹配了。
KMP 算法 比较指针不回溯仅仅是后移模式串。
每次不匹配的时候找之前已匹配部分中模式串的最长公共前后缀。
前缀与后缀相同所以T里面与P的后缀a匹配的那个a一定也与P中的前缀a匹配所以直接从前缀后面的b开始匹配就行了
也就是碰到某个不匹配的时候我这个模式串要从最长前缀后滑动到最长后缀的位置其实就是比较指针 j 从最长前缀移动到最长后缀的位置。而保存这个位置的数组就是 next 数组。 next数组——前缀表prefix table
前缀表是用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
next数组既可以就是前缀表也可以是前缀表统一减一右移一位初始位置为-1。 帮你把KMP算法学个通透求next数组代码篇_哔哩哔哩_bilibili
构造next数组
定义一个函数getNext来构建next数组函数参数为指向next数组的指针和一个字符串。定义一个函数getNext来构建next数组函数参数为指向next数组的指针和一个字符串。 int* next 的含义
void getNext(int* next, const string s); int* next 是一个指向整型数组的指针。 它表示 next 是一个数组而不是单个整数。 在函数内部可以通过 next[i] 访问数组的第 i 个元素。
getNext(next[0], needle); 的语义 next 是一个整型数组例如 int next[10];。 next[0] 是数组 next 的首地址类型是 int*。 通过 int* next 参数函数可以访问和修改整个数组。 next数组里存储的是对应位置最长公共前后缀值、当前后缀不相同时j回退到next[j-1]值对应坐标需要j大于等于1时。相同时j更新next。 class Solution {
public://求next数组void getNext(int* next, const string s){//初始化int i 1;//后缀末尾位、主串所在int j 0;//前缀末尾位、最长公共前后缀长度next[0] 0;for(int i 1; is.size(); i){while(j 1 s[i] ! s[j]){j next[j-1];//当前后缀不相同j回退到next[j-1]值对应坐标}if(s[i] s[j]){j;//前后缀相等最长公共前后缀长度1、准备比较下一位是否相等}next[i] j;//更新next数组值}}int strStr(string haystack, string needle) {if(needle.size() 0){return 0;}vectorint next(needle.size());getNext(next[0], needle);int j 0;for(int i 0; i haystack.size(); i){while(j 0 haystack[i] ! needle[j]){j next[j-1];}if(haystack[i] needle[j]){j;}if(j needle.size()){return (i-needle.size()1);}}return -1;}
};
