字符串模式匹配（朴素模式匹配算法与KMP算法）

文章目录什么是字符串的模式匹配两种模式匹配算法第一种朴素模式匹配算法BF方式一定位操作的方式实现方式二数组下标实现朴素模式匹配算法时间复杂度第二种KMP算法朴素模式匹配的优化求next数组预处理模式匹配时间复杂度求模式串的next数组手算练习next数组的优化nextval数组手算练习什么是字符串的模式匹配在主串 N 中查找 M 子串。NM 主串的长度可能远大于子串的长度两种模式匹配算法字符串模式匹配在主串中找到与模式串相同的子串并返回其(第一个元素)所在位置。子串是主串的一部分一定存在于主串中模式串不一定能在主串中找到。第一种朴素模式匹配算法BF主串长度为n模式串长度为m。朴素模式匹配算法将主串中所有长度为m的子串最多对比n-m1个子串依次与模式串对比直到找到一个完全匹配的子串(返回其第一个元素的位置位序)或将所有的子串都不匹配为止。算法思想“枚举所有可能的位置逐一尝试匹配。”主串长度为n模式串长度为m。算法从主串的第1个字符开始截取长度为m的子串与T比较。若匹配则返回当前位置若不匹配则从主串的下一个位置重新开始比较。直到主串剩余长度不足m则匹配失败返回0。方式一定位操作的方式实现// 定位操作intIndex(SString S,SString T){// S为主串T为子串inti1;intnS.length,mT.length;// 获取串的长度SString Sub;// 用于暂存子串// 最多对比 n-m1个子串while(in-m1){// 边界条件剩余长度必须 m// 取出从位置i开始长度为m的子串SubString(Sub,S,i,m);// 调用已实现的求子串 取出长度为m的子串// 子串和模式串对比若不匹配则匹配下一个子串if(StrCompare(Sub,T)0){returni;// 匹配成功}i;// 不匹配则往后移动一位继续查找}return0;// 未找到 S中不存在与T相等的子串}方式二数组下标实现朴素模式匹配算法不使用字符串的基本操作直接通过数组下标实现朴素模式匹配算法。intIndex(SString S,SString T){inti1,j1;// i 遍历主串S j 遍历子串T// 当iS.length则结束循环while(iS.lengthjT.length){if(S.ch[i]T.ch[j]){// 1. 匹配成功指针后移继续匹配i;j;}else{// 2. 匹配失败i 回溯j 重置ii-j2;// 核心回溯公式j1;}}if(jT.length)// 3. 子串全部匹配完returni-T.length;// 返回起始位置elsereturn0;}时间复杂度设主串长度为n模式串长度为m则最坏的时间复杂度为O(nm).第二种KMP算法朴素模式匹配的优化利用 不匹配的字符之前前面的这些元素一定是和模式串一致的可以直接选择从下一个不同的地方开始匹配。** i (主串指针)不动即主串指针i不用回溯j变化**求next数组预处理根据模式串T求出next数组。next数组之和模式串有关与主串无关。// 求模式串 T 的 next 数组位序从1开始voidget_next(SString T,intnext[]){inti1,j0;next[1]0;// 1. next[0] 无脑写0while(iT.length){// 注意i 从1遍历到 length-1因为 next[length] 需要在循环内求if(j0||T.ch[i]T.ch[j]){// 2. 匹配或退无可退i;j;next[i]j;// 3. 记录当前 i 位置的 next 值}else{jnext[j];// 4. 回溯 j利用已求得的 next 数组}}}模式匹配利用next数组进行匹配主串指针不回溯// KMP 匹配算法主串 S模式串 T已求好的 next 数组intIndex_KMP(SString S,SString T,intnext[]){inti1,j1;while(iS.lengthjT.length){// 1. 若 j0表示第一个字符都不匹配i 必须后移一位// 2. 若当前字符匹配继续比较下一对if(j0||S.ch[i]T.ch[j]){i;j;}else{// 3. 失配i 不动j 回溯到 next[j]jnext[j];}}if(jT.length)returni-T.length;// 匹配成功elsereturn0;}时间复杂度KMP算法最坏时间复杂度O(mn)其中预处理求next数组时间复杂度O(m)模式匹配模式匹配过程最坏时间复杂度O(n)求模式串的next数组手算练习next[1]都无脑写0next[2]都无脑写1其他next在不匹配的位置前划一刀分界线模式串一步一步往后退向右走直到分界线之前左边都“能对上”或模式串完全跨过分界线为止。此时j 指向哪儿则next数组值就是多少。next数组的优化nextval数组手算练习// 求优化后的 nextval 数组voidget_nextval(SString T,intnextval[]){inti1,j0;nextval[1]0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i;j;// 核心优化若 i 和 j 位置的字符相等则继续递归if(T.ch[i]!T.ch[j]){nextval[i]j;// 不同直接赋值}else{nextval[i]nextval[j];// 相同用 nextval 覆盖}}else{jnextval[j];// 回溯时也用 nextval}}}手算解题先求next数组再由next数组求nextval数组。nextval[1]0;// 从next[2]开始for(intj2;jT.length;j){if(T.ch[next[j]]T.ch[j])nextval[j]nextval[next[j]];// 优化部分elsenextval[j]next[j];}