电子代加工东莞网站建设,网站建设方案书 doc,wordpress searchform.php,网站质量需求4.2 串的模式匹配
4.2.1_朴素模式匹配算法
字符串模式匹配#xff1a;在主串中找到与模式串相同的⼦串#xff0c;并返回其所在位置
主串⻓度为n#xff0c;模式串⻓度为 m 朴素模式匹配算法#xff1a;将主串中所有⻓度为m的⼦串依次与模式串对⽐#xff0c;直到找到⼀…4.2 串的模式匹配
4.2.1_朴素模式匹配算法
字符串模式匹配在主串中找到与模式串相同的⼦串并返回其所在位置
主串⻓度为n模式串⻓度为 m 朴素模式匹配算法将主串中所有⻓度为m的⼦串依次与模式串对⽐直到找到⼀个完全匹配的⼦串 或所有的⼦串都不匹配为⽌。 最多对⽐ n-m1 个⼦串
Index(S,T)定位操作。若主串S中存在与串T值相同的⼦串则返回它在主串S中第⼀次出现 的位置否则函数值为0 接下来不使用字符串的基本操作直接通过数组下标实现朴素模式匹配算法
// 在主串S中找到与模式串T相同的子串并返回其位序否则返回0
int Index(SString S, SString T){ int i1, j1; while(iS.length jT.length){ if(S.ch[i] T.ch[j]){ //如果i里面存的字符和j里面存的相同的话i; j; //继续比较后继字符}else{ ii-j2; //i指针指向下一个子串的起始位置j1; //j指针后退回到第一个位置重新开始匹配 } } if(jT.length) return i-T.length; else return 0;
}设主串⻓度为 n模式串⻓度为 m则 最坏时间复杂度 O(nm)
最坏的情况每个⼦串都要对⽐ m 个字符共 n-m1 个⼦串复杂度 O((n-m1)m) O(nm) 4.2.2_1_KMP算法
朴素模式匹配算法的缺点 ⼀旦发现当前这个⼦串中某个字符不匹配就只能转⽽匹配下⼀个⼦串从头开始 用代码实现这个处理逻辑 可以用一个next数组来存储让模式串指针指向的位置 next数组只和短短的模式串 有关和长长的主串⽆关
KMP算法当子串和模式串不匹配时主串指针 i 不回溯模式串指针 jnext[j]。
KMP算法最坏时间复杂度 O(mn) 其中求 next 数组时间复杂度 O(m) 模式匹配过程最坏时间复杂度 O(n)
KMP算法的代码实现
// 获取模式串T的next[]数组
void getNext(SString T, int next[]){ int i1, j0; next[1]0; while(iT.length){ if(j0 || T.ch[1]T.ch[j]){ i; j; next[i]j; }else jnext[j]; }
}// KPM算法求主串S中模式串T的位序没有则返回0
int Index_KMP(SString S, SString T){ int i1, j1; int next[T.length1]; getNext(T, next); while(iS.length jT.length){ if(j0 || S.ch[i]T.ch[j]){ //如果主串的元素和模式串的元素相等或j等于0时i; j; //i和j继续比较后继字符}else jnext[j]; //模式串向后移动} if(jT.length) return i-T.length; //j大于模式串长度说明匹配成功elsereturn 0;
}int main() {SString S{ababcabcd, 9};SString T{bcd, 3};printf(%d , Index_KPM(S, T)); //输出9
}KMP算法精髓利用已经匹配过的模式串的信息求出next数组→利用next数组进行匹配(主串指针不回溯
4.2.2_2_求next数组
next数组的作⽤当模式串的第 j 个字符失配时从模式串的第 next[j] 的继续往后匹配
任何模式串第⼀个字符不匹配时只能匹配下⼀个⼦串因此next[1]都⽆脑写 0 第2个字符不匹配时应尝试匹配模式串的第1个字符 因此next[2]都⽆脑写 1 接下来的字符在不匹配的位置前划一根分界线模式串一步一步往后退直到分界线前的“对的上”或模式串完全越过分界线位置,如下面为第3个字符不匹配的情况第四个字符不匹配 第五个字符不匹配 第六个字符不匹配
4.2.3_KMP算法的进一步优化 第3个字符和第1个字符相同所以 可以直接跳到next[1]指向的位置第5个字符跟第2个字符相同直接跳到next[2]指向的位置
void getNextval(SString T, int nextval[]){int i1,j0;nextval[1]0;while(iT.length){if(j0 || T.ch[i]T.ch[j]){i; j;if(T.ch[i]!T.ch[j])nextval[i]j;elsenextval[i]nextval[j];}elsejnextval[j];}
}
