南宁百度网站推广,计算机网站建设与推广,html网页制作个人简介,包装公司网站模板下载KMP算法是计算机科学中的一种字符串匹配算法#xff0c;KMP是三个创始人名字首字母 题目
AcWing - 算法基础课
前置知识点
KMP算法是一种高效的字符串匹配算法#xff0c;算法名称取自于三位共同发明人名字的首字母组合。该算法的主要使用场景就是在字符串#xff08;也叫…KMP算法是计算机科学中的一种字符串匹配算法KMP是三个创始人名字首字母 题目
AcWing - 算法基础课
前置知识点
KMP算法是一种高效的字符串匹配算法算法名称取自于三位共同发明人名字的首字母组合。该算法的主要使用场景就是在字符串也叫主串中的模式串也叫子串定位问题常见的有“求子串出现的起始位置”、“求子串的出现次数”等。
前缀和后缀
假设一个字符串“ababa
他的前缀就是a,ab,aba,abab ababaababaababaababa
他的后缀就是a,ba,aba,baba ababaababaababaababa
前缀和后缀的最大长度是原字符串长度-1
思路
最浅显易懂的 KMP 算法讲解_哔哩哔哩_bilibili
F03【模板】KMP 算法——信息学竞赛算法_哔哩哔哩_bilibili
给定一个主串S模式串P求P在S中出现的位置
普通暴力枚举
一个字符一个字符的双指针枚举一旦发现不同 主串又要从第二个开始匹配子串要从头开始匹配 缺点时间复杂度太高
kmp优化思路
在比对失败时我们已经知道曾经读过哪些字符了 已经匹配的子串有相同的后缀 前缀那我们是不是可以保留相同的前缀再去查找不同的剩下的字符串
如下图主串保留的绿色实际上是匹配的子串的后缀子串里保留的绿色部分就是匹配的子串的前缀
他们是相同的则可以把主串里匹配的子串的后缀视为子串前缀继续在主串查找相同前缀后面的字符串 next数组使用
我们已经知道kmp的优化思路那么如何将知道该保留的前缀呢再暴力双指针循环太麻烦
kmp三个人提出了next数组我们先不看如何实现先看如何使用next数组功能
下图是一个初始状态 kmp算法匹配失败时去看最后一个匹配成功的子串的字符对应的next数组里的值 查到对应的值后我们移动子串跳过next数组里的值对应的字符个数例如值是2我们就跳过前两个字符 我们发现跳过的这两个字符确实能和主串指针指向位置前的两个字符对应
所以继续枚举即可不需要从头枚举 这样我们永远不需要回退主串指针一次遍历主串就可以找到匹配子串 再看一下 如果子串对应next是0时 如果为0,也是从头开始匹配子串没有相同的前缀和后缀则子串一定不在已经遍历过的主串里有
则已经遍历过的主串里的字符一定没有子串的子串所以主串之前的部分可以直接舍弃不用移动主串指针 推导next数组
next数组中的值实际上就是子串以当前字符串结尾在当前字符串中最长的前缀后缀相同的字符串长度
如下图 ABAB最长的相同前缀后缀该前缀或者后缀的长度是2
我们现在知道next的数组里的值代表什么了
那我们想一下如何推导出next数组里的值
在后缀下一个字符和前缀后一个字符相同时我们只需要把next数组对应的值1然后填入即可 那在不同时应该怎么办循环遍历可以但是时间复杂度较高
举例上图再往下走一个 C和B不同如何求B的对应的next值 下位字符不同没办法构成更长的相同前后缀我们看看有没有更短的前后缀 我们可以发现确实存在更短的两位的前后缀但是这步在程序中如何体现暴力求解似乎时间复杂度有点高
其实我们next数组里还有信息也就是next[i]3则子串前3个数和i-3到i这两个字符串是相同的
字符串前三个字符和i-3到i就是前后缀前三个数和后三个数 也就是右边的后缀其实等于左边的前缀那我们其实可以忽略中间其他的值直接去找到最左边
为什么不会有漏第一右边的后缀和左边的前缀完全相等
第二后缀第四个字符和前缀第四个字符不同所以不会比右边的后缀或左边的前缀更长也就不会用更多字符 这样就相当于是求ABAB的前后缀
第三个A对应的值是1B是字符串ABAB后缀的第二个字符因为A对应的是1)
比较B和前缀的第二个字符是否相等 相等则在B所处位置对应的next数组的值1
B对应的next的数组的上一位的值是通过第三个A获取的但是实际上和他组成后缀的是倒数第二个A 实际上是这样得到的next对应的值抽象上是和第三个A组成的前后缀
因为倒数第二个A对应的next的值为3也就是和前三个字符前缀完全相等
所以可以直接拿第二个A的next计算因为前三个字符和后三个字符这说的字符串next3对应的A完全一样
前三个有的字符后三个都有所以B可以和后三个字符组成的后缀和前三个字符也可以组成相同的后缀
后三个字符代表的next值代表的前后缀相同的长度又太长利用前三个字符代表的前后缀长度即可完成回退 代码实现
next[i]代表子串p[1,i]相同前后缀的最大长度
i代表的指针永远不往前回退指向的是后缀的最后一个字符
j代表的指针可以通过next数组回退指向的是前缀最后一个字符
注next在c中有关键字所以使用ne[]
next数组推导实现
ne[1]0;
//两个字符串数组实际上都是从1开始
//i等于2是因为指向第二个字符即可至少两个字符才有前后缀
//j0,因为j从j1开始比也就是j0是为了j从1开始
for(int i2,j0;in;i){ //j不为0为0表示回到的子串第一个数的位置//i代表目前指到的位置j代表相同前后缀的前缀的最后一个字符的位置//如果下位字符不同时回退到j的值代表的前ne[j]位//上图中说前缀后缀完全相等j回到相同的前缀的最后一个字符的位置//看ne[j]的下一位p[j]和i指向的字符是否相等//相等结束循环否则继续直到相等或者j0(回退到第一个字符串)while(jp[i]!p[j1])jne[j];//如果是相等而不是j回退到了0则j,表示长度1//j的值是ne[j]的值,j 就是 jne[j]1,if(p[i]p[j1])j;//记录下j的值j现在指向的是相同前后缀的前缀的最后一个字符//代表的值是最长相同前后缀长度//把这个值加在ne[i]指针上指向的是相同前后缀后缀的最后一个字符ne[i]j;
}
子串位置查找实现查找主串出现子串的起始位置 //推导子串出现位置,这次i等于1是因为此循环判断的不是前后缀相同而是判断是否为子串//因为两个完全一样的字符串也互相为子串子串第一个数有可能从i1,j1就开始了//所以这里要令i1for(int i1,j0;im;i){//跳跃式找到主串现在指向的值在子串中存在的位置while(js[i]!p[j1])jne[j];//i指向主串的字符和子串的字符下一个字符相等,则可以再推进走一步if(s[i]p[j1])j;if(jn)//长度一致找到子串{couti-j ;//返回子串起始位置//可省略意思是将j回退到除本身外最大的相同前后缀长度,避免下个循环j1越界jne[j];}}
整合代码
AcWing - 算法基础课
#includeiostream
using namespace std;
const int N 100010;
char p[N],s[N*10];
int ne[N];
int n,m;
int main(){cin n p 1 m s 1;ne[1]0;//推导nxet数组for(int i2,j0;in;i){while(jp[i]!p[j1])jne[j];if(p[i]p[j1])j;ne[i]j;}//推导子串出现位置for(int i1,j0;im;i){//跳跃式找到主串现在指向的值在子串中存在的位置while(js[i]!p[j1])jne[j];if(s[i]p[j1])j;if(jn)//长度一致找到子串{couti-j ;//返回子串起始位置//可省略意思是将j回退到除本身外最大的相同前后缀长度,避免下个循环j1越界jne[j];}}return 0;
}
