微信网站搭建哪家好,服务器租用收费,3d建模好学吗,石家庄最新状况文章目录 0#xff09;概述1#xff09;求解next数组2#xff09;求解匹配位置的核心函数3#xff09;完整代码 0#xff09;概述
在做模式串与文本串的匹配问题时#xff0c;匹配失败时#xff0c;如果每次都只向后递进一位#xff0c;时间复杂度为 O ( n m ) O(nm… 文章目录 0概述1求解next数组2求解匹配位置的核心函数3完整代码 0概述
在做模式串与文本串的匹配问题时匹配失败时如果每次都只向后递进一位时间复杂度为 O ( n m ) O(nm) O(nm)很容易被卡成 O ( m × n ) O(m×n) O(m×n) 所以为了降低字符串匹配算法的时间复杂度对模式串中的每一位设置唯一的特定变化位置这个在失配之后的特定变化位置可以帮助我们利用已有的数据不用从头匹配从而节约时间用 n e ne ne 数组记录到它为止的模式串前缀的真前缀和真后缀最大相同的位置当 i 1 i1 i1 或 i 2 i2 i2 时 n e [ i ] ne[i] ne[i] 的返回值是 1 1 1即 n e [ 1 ] n e [ 2 ] 1 ne[1]ne[2]1 ne[1]ne[2]1 (当下标从 1 1 1 开始)因为当 n 1 n1 n1 时只有一个元素此时无前后缀当 n 2 n2 n2 时两个元素一个是前缀一个是后缀仍然回溯到第一个位置
1求解next数组
// 求next数组的过程[s1与自己匹配,通过前后缀来更新ne数组]
for(int i2,j0;ilen1;i)
{while (j s1[i]!s1[j1])jne[j]; // 如果不匹配的话,j就一直后退if(s1[i]s1[j1])j; // 如果当前匹配成功的,j向前递推一位ne[i]j; // 记录并且更新当前j的长度
}当看不懂或者忘了的时候建议自己调试模拟跟踪一遍 因为 n e ne ne 数组是全局初始化 w h i l e ( ) while() while() 语句中的 j j j 保证了 n e [ 1 ] n e [ 2 ] ne[1]ne[2] ne[1]ne[2] 注意next数组的值是根据模式串的前缀和后缀的最大相同位置来的所以匹配自己。
2求解匹配位置的核心函数
// 求匹配的过程[i遍历文本串]
for(int i1,j0;ilen2;i )
{// 如果不匹配的话,j回退while(j s2[i]!s1[j1])jne[j];// 如果相等的话,j向前递推一位if(s2[i]s1[j1])j;// 刚好长度相等的话说明匹配上了,把下标打印出来if(jlen1){// 文本串的位置减去长度即为下标,加1得到位置printf(%d ,i-len11);// 模板串在模式串中出现的位置可能是重叠的// 需要让j回退到一定位置,再让i加1继续进行比较// 回退到ne[j]可以保证j最大,即已经成功匹配的部分最长jne[j];}
}核心实现和求解 n e x t next next 数组的函数差不多主要是是模式串和文本串之间的匹配当 j l e n 1 jlen1 jlen1 的时候说明大小相等即匹配上了这个时候把相应的下标位置输出出来同时 j j j 还是要回溯因为怕遇到位置重叠的情况。
3完整代码 题目链接P3375 【模板】KMP - 洛谷 #includebits/stdc.h
using namespace std;
const int N10;
int len1,len2; // n是模板串长度,m是文本串
int ne[N]; // next[i] 就是使子串 s2[0···i] 有最长相等前后缀的前缀的最后一位的下标
char s1[N],s2[N]; // s1[]存储模式串,s2[]存储文本串
// 计算p[]在s[]中出现的位置
// ne代表next数组,因为next在C中是关键字
int main()
{cins11s21; // 先输入模式串,再输入文本串[从下标1开始]len1strlen(s11);len2strlen(s21);coutlen1 len2endl;// 求next数组的过程[s1与自己匹配,通过前后缀来更新ne数组]for(int i2,j0;ilen1;i){while (j s1[i]!s1[j1])jne[j]; // 如果不匹配的话,j就一直后退if(s1[i]s1[j1])j; // 如果当前匹配成功的,j向前递推一位ne[i]j; // 记录并且更新当前j的长度}// 求匹配的过程[i遍历文本串]for(int i1,j0;ilen2;i ){// 如果不匹配的话,j回退while(j s2[i]!s1[j1])jne[j];// 如果相等的话,j向前递推一位if(s2[i]s1[j1])j;// 刚好长度相等的话说明匹配上了,把下标打印出来if(jlen1){// 文本串的位置减去长度即为下标printf(%d ,i-len1);// 模板串在模式串中出现的位置可能是重叠的// 需要让j回退到一定位置,再让i加1继续进行比较// 回退到ne[j]可以保证 j 最大,即已经成功匹配的部分最长jne[j];}}// 还需要把next数组输出出来for(auto num:ne) coutnum ;coutendl;return 0;
}
