网站漏洞 在线扫描怎样制作微信小程序卖东西

当前位置： 首页 > news >正文

网站漏洞 在线扫描,怎样制作微信小程序卖东西,濮阳网警,库存管理系统软件一.回顾#xff1a;KMP算法基于朴素模式匹配算法优化而得来的 朴素模式匹配算法核心思想#xff1a;把主串中所有长度与模式串长度相等的子串与模式串进行对比#xff0c;直到找到第一个完全匹配的子串为止#xff0c;如果当前尝试匹配的子串在某一个位置匹配失败#xf… 一.回顾KMP算法基于朴素模式匹配算法优化而得来的 朴素模式匹配算法核心思想把主串中所有长度与模式串长度相等的子串与模式串进行对比直到找到第一个完全匹配的子串为止如果当前尝试匹配的子串在某一个位置匹配失败就立即进行下一个子串的匹配而且是从下一个子串的头部开始一一匹配 例1 模式串的最后一个字符与主串中第一个和模式串长度相等的子串匹配失败 模式串与主串中第二个与模式串长度相等的子串比较开始从2号字符开头的子串进行比较之所以开始匹配2号字符开头的子串且从2号字符开始比较是因为在主串里的字符到底是什么无法得知所以只能从主串里与模式串长度相等的子串的第一个字符依次往后匹配 如果以2号字符开头的这个子串在某个字符上与模式串匹配失败同理由于主串里的字符未知因此只能尝试匹配以3号字符开头的子串并且要从3号字符开始依次往后与模式串进行对比因为主串里包含的内容不得而知 之后以此类推找主串中是否有要找的模式串。 换一种思路 模式串的最后一个字符与主串中第一个和模式串长度相等的子串匹配失败那么该子串中除了最后一个字符外都与模式串中除了最后一个字符外匹配成功因此本例中模式串匹配到第6个字符才发现匹配失败这种情况下就可以从模式串中得知主串中的前几个字符的内容只有最后一个字符不知道所以就要利用好此时主串中已知的字符 根据朴素模式匹配算法的思想如果当前的子串匹配失败就要取下一个符合要求的子串与模式串进行对比此时已经知道主串中前几个字符的信息因此就会发现模式串的第一个字符就与此时要匹配的子串不匹配所以当前的子串就没必要继续匹配下去直接进行第三个符合要求的子串进行与模式串匹配 现在的子串也是知道前几个字符的信息本例中可以知道该子串前3个字符为aab第一个字符可以和模式串第一个字符匹配第二个字符就与模式串不匹配了所以这个子串也没有必要继续匹配了 同理开始下一个子串的匹配该子串的前两个字符是已知的而且前两个字符匹配成功但该子串里的第三个字符就不得而知了所以对于现在的这个字符来说前两个字符匹配成功而第三个字符是否匹配成功暂时还不知道因此一开始只需要从第三个字符开始往后检查匹配就可以了 总结 如本例中模式串在与第一个子串进行匹配时如果发现最后一个字符不匹配那么就意味着前5个字符已得知此时主串中以标记2为开头的子串和以标记3为开头的子串就无需匹配了可以直接对比以标记4为开头的子串而且在对比以标记4为开头的子串时只需要从第三个字符开始检查即可因为前两个元素已经确定和模式串匹配成功这样就省去了大量的无效匹配 KMP算法的思想利用好模式串本身隐含的信息要确定模式串的某一个元素发生匹配失败时接下来要如何处理显然最终的结论并不依赖主串的内容和匹配的主串的哪一个位置并没有关系只和模式串的内容有关 例2 主串中第一个符合要求的子串与模式串匹配时在第5个字符上匹配失败 此时主串中的前4个元素的具体信息是可以确定的与模式串一致从第5个元素开始后面的信息暂时不确定 第一个子串匹配失败开始下一个子串的匹配显然匹配失败 继续下一个子串的匹配显然也不行 继续下一个子串的匹配已知的字符匹配成功而未知的字符能否匹配成功暂时不得而知所以本例中可以从该子串的第二个字符开始检查匹配 例3 主串中第一个符合要求的子串与模式串匹配时在第4个字符上匹配失败 此时主串中的前3个元素的具体信息是可以确定的与模式串一致从第4个元素开始后面的信息暂时不确定 第一个子串匹配失败开始下一个子串的匹配显然匹配失败 继续下一个子串的匹配已知的字符匹配成功而未知的字符能否匹配成功暂时不得而知所以本例中可以从该子串的第二个字符开始检查匹配 例4 主串中第一个符合要求的子串与模式串匹配时在第3个字符上匹配失败 此时主串中的前2个元素的具体信息是可以确定的与模式串一致从第3个元素开始后面的信息暂时不确定 第一个子串匹配失败开始下一个子串的匹配已知的元素当中匹配失败 继续下一个子串的匹配此时已知的元素全部用完 例5 主串中第一个符合要求的子串与模式串匹配时在第2个字符上匹配失败 此时主串中的第1个元素的具体信息是可以确定的与模式串一致从第2个元素开始后面的信息暂时不确定 继续下一个子串的匹配此时已知的元素全部用完 例6 主串中第一个符合要求的子串与模式串匹配时在第1个字符上就匹配失败此时就只能尝试匹配下一个符合要求的子串了 前面的5个例子中都是主串指针不变模式串指针变本例中为了和前5个例子中的处理逻辑类似可以先让模式串指针为0即指向模式串第一个元素的前一个位置之后让主串指针和模式串指针都自增即可这样就可以实现主串指针和模式串指针同时后移 总结 整合 第一个子串与模式串在第6个字符上匹配失败按照朴素模式匹配算法需要主串指针回溯模式串指针变为1 按照刚才的过程即利用主串指针不回溯直接主串指针不变修改模式串指针即可省去了无效的对比 进行此次的匹配最终全部匹配成功主串指针也无需回溯大大提高了查找效率 通常来说主串要比模式串长很多因此用主串指针不回溯的方法是非常高效的。 例7 最终会因为模式串指针超出指定范围而停止。 二.利用代码实现主串指针不回溯的查找算法 可以利用数组该数组记录当某个元素匹配失败时模式串指针应该指向的值注当第一个元素就匹配失败时就要把模式串指针设为0 next数组记录当某个元素匹配失败时模式串指针应该指向的值 i为主串指针j为模式串指针 S为主串T为模式串 例如j为6代表此时匹配到模式串里的第6个字符如果此时第6个字符匹配失败那么根据jnext[j]此时j更改为3 利用next数组进行匹配(主串指针不回溯)的代码形参中S为主串T为模式串next数组记录当某个元素匹配失败时模式串指针应该指向的值函数体中i为主串指针j为模式串指针i和j都从1开始即从头部开始匹配S.length表示主串的长度T.length表示模式串的长度S.ch[i]T.ch[j]表示此时主串的元素等于模式串的元素 三.朴素模式匹配算法 v.s. KMP算法 KMP算法相比于朴素模式匹配算法多了一个next数组以及对模式串指针为0时的判断有了next数组就不需要主串指针回溯只需要修改模式串的指针即可 主串的长度为n由于主串指针不回溯所以模式匹配过程最坏时间复杂度就是O(n)即把整个主串都走了一遍最终算整个算法的时间复杂度时只需要相加即可 KMP算法最坏时间复杂度为O(mn) KMP算法在效率上要优于朴素模式匹配算法 四.求next数组(next数组记录当某个元素匹配失败时模式串指针应该指向的值) 注next数组0索引上不存数据从1索引开始 next数组的长度等于模式串长度加一因为next数组存储数据的下标要和模式串的下标一一对应此时模式串下标规定从1开始而数组下标却从0开始所以next数组的长度等于模式串长度加一由上图也可知 比如next[1]代表模式串第一个字符在next数组中next[1]的含义是当模式串的第一个字符发生匹配失败时模式串指针应该指向哪个位置 任何模式串都一样第一个字符不匹配时只能匹配主串里下一个符合要求的子串因此往后余生next[1]都无脑写0 任何模式串都一样第二个字符不匹配时应尝试匹配模式串的第一个字符因此往后余生next[2]都无脑写1
例一 求next[1]若模式串的第一个字符匹配失败根据之前的分析此时模式串指针的值赋值为0然后模式串指针和主串指针同时自增即开始匹配往后的模式串和主串里的子串所以next[1]为0 求next[2]若模式串的第二个字符匹配失败意味着这时无法得知模式串的第二个字符所在的位置对应的主串里的该位置的字符那么就只能让模式串往后滑动一位也就是让模式串指针为1即next[2]为1 求next[3]若模式串的第三个字符匹配失败此时可以由模式串得知主串里的两个字符(如下图)即分界线左边的两个字符在分界线的左边的前两个字符一个一个往后移动进行比对如果比对成功就进行下一个字符的比对如果失败直接后移模式串比对。例如本例中先移动一个字符发现不匹配然后继续往后移模式串此时整个模式串就全部移动到分界线的右边了而在分界线的右边主串的内容就不得而知了因此就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对因此当模式串第三个字符匹配失败时可以直接让模式串指针的值为1即next[3]为1 求next[4]若模式串的第四个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前三个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对根据题意由于无法匹配成功最终模式串会全部移动到分界线右边而且分界线右边的字符无法确定所以就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对所以当模式串第四个字符匹配失败时可以让模式串指针的值为1即next[4]为1 求next[5]若模式串的第五个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前四个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对一边移动一边比对最终当分界线左边只剩下一个字符时开始匹配成功由于分界线右边的字符未知所以有必要开始模式串第二个字符的比对因此当模式串第五个字符匹配失败时可以让模式串指针的值为2即next[5]为2 求next[6]若模式串的第六个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前五个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对一边移动一边比对根据题意由于无法匹配成功模式串最终会全部移动到分界线右边而且分界线右边的字符无法确定所以就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对所以当模式串第六个字符匹配失败时可以让模式串指针的值为1即next[6]为1 到此求出了字符串google的next数组。 应用例一中通过字符串google求出的next数组 首先模式串的第六个字符匹配失败根据求出来的next数组模式串指针指向1 此时模式串的第一个字符匹配失败根据求出来的next数组模式串指针指向0 同时模式串指针和主串指针要自增也就是开始匹配下一个子串 此时模式串的第五个字符匹配失败根据求出来的next数组模式串指针指向2 如下 比对后最终匹配成功 例二 求next[3]若模式串的第三个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前两个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对一边移动一边比对根据题意由于无法匹配成功模式串最终会全部移动到分界线右边而且分界线右边的字符无法确定所以就有必要把此时主串指针所指的元素和模式串指针所指的元素进行比对所以当模式串第三个字符匹配失败时可以让模式串指针的值为1即next[3]为1 求next[4]若模式串的第四个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前三个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对一边移动一边比对当模式串移动到在分界线左边只剩下一个字符时开始匹配成功由于分界线右边的字符无法确定所以有必要开始模式串第二个字符的比对因此当模式串第四个字符匹配失败时可以让模式串指针的值为2即next[4]为2 求next[5]若模式串的第五个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前四个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对一边移动一边比对当模式串移动到在分界线左边剩下两个字符时开始匹配成功由于分界线右边的字符无法确定所以有必要开始模式串第三个字符的比对因此当模式串第五个字符匹配失败时可以让模式串指针的值为3即next[5]为3 求next[6]若模式串的第六个字符匹配失败此时可以在匹配失败的字符左边画一条分界线主串中这条分界线左边的前五个字符可以确定而分界线右边的字符就无法确定接下来需要模式串一步一步往右移动来比对一边移动一边比对当模式串移动到在分界线左边剩下三个字符时开始匹配成功由于分界线右边的字符无法确定所以有必要开始模式串第四个字符的比对因此当模式串第六个字符匹配失败时可以让模式串指针的值为4即next[6]为4 到此求出了模式串T的next数组。 五.求next数组的总结 注next数组0索引上不存数据从1索引开始 六.next数组的优化思路利用之前已求出next数组的模式串T即abaabc 例一 若此时在第三个字符匹配失败 根据next数组此时模式串指针应指向1即j为1 由于第三个字符匹配失败所以主串指针所指的字符和模式串指针所指的字符是不相等的既然不相等又此时模式串指针所指的是模式串的第三个字符a说明主串指针所指的第三个字符一定不是a因此当第三个字符匹配失败时接下来需要让模式串指针指向1但这一次的匹配一定会失败因为模式串指针此时所指的字符是第一个字符a这是已知的而此时主串指针所指的元素虽然未知但它一定不是a第一个字符匹配失败时需要模式串指针指向0然后模式串指针和主串指针自增 所以一开始发现模式串第三个字符和主串第三个字符匹配失败时又因为模式串里的第一个字符和第三个字符相等所以模式串里的第一个字符和主串里的第三个字符也一定会匹配失败因此一开始发现模式串第三个字符和主串第三个字符匹配失败时就可以直接让模式串指针指向0因为如果让模式串指针指向1时意味着接下来是让模式串第一个字符和主串第三个字符开始匹配根据之前的分析该匹配注定失败当第一个字符匹配失败时应该让模式串指针指向0所以最好的处理方式就是直接让模式串指针指向0这样就可以跳过多余的模式串第一个字符匹配主串第三个字符 最终优化后当第三个字符匹配失败时直接让模式串指针指向0然后模式串指针和主串指针自增意味着跳过了多余的模式串第一个字符匹配主串第三个字符 例二 若此时在第五个字符匹配失败 根据next数组此时模式串指针应指向2即j为2 由于第五个字符匹配失败所以主串指针所指的字符和模式串指针所指的字符是不相等的既然不相等又此时模式串指针所指的是模式串的第五个字符b说明主串指针所指的第五个字符一定不是b因此当第五个字符匹配失败时接下来需要让模式串指针指向2但这一次的匹配一定会失败因为模式串指针此时所指的字符是第二个字符b这是已知的而此时主串指针所指的元素虽然未知但它一定不是b第二个字符匹配失败时需要模式串指针指向1 最终优化后当第五个字符匹配失败时直接让模式串指针指向1意味着跳过了多余的模式串第二个字符匹配主串第五个字符 最终优化后演示 例三 若此时在第六个字符匹配失败可以确定主串第六个字符一定不是c 根据next数组此时模式串指针应指向3即j为3模式串第三个字符为a主串里的第六个字符一定不是c但是否是a就无法确定了所以此时就有必要进行匹配判断因此当六个字符匹配失败时让模式串指针指向3是有必要的无需继续优化 结论当匹配失败时判断模式串指针要指向的下一个模式串字符和原本失配的字符是否相等如果这两个字符不相等next数组的值保持不变如果这两个字符相等此时可以更改next数组的值实现优化 KMP算法的进一步优化本质是优化next数组 nextval数组其实就是next数组的优化也可以把nextval数组理解为新的next数组nextval数组可以命名为next数组 七.求nextval数组nextval数组其实就是next数组的优化也可以把nextval数组理解为新的next数组nextval数组可以命名为next数组 注nextval数组0索引上不存数据从1索引开始nextval数组1索引上的数据固定为0即nextval[1]0原理和next数组1索引上的数据固定为0的原理一样从2索引开始就需要一步一步推导 练习1 函数解读 j为模式串指针T.length为模式串的长度T.ch[j]为模式串T在j索引上的字符 一般都是先求出next数组再求nextval数组 j代表模式串指针当前所指的字符next[j]代表模式串指针应更改为所指向的字符 next数组和nextval数组所包含的内容都是一样的即把当前模式串指针的值修改为下一次要指向的值 该函数中nextval数组存储的值都是从next数组得出的也就是说nextval的元素是next[j] 如果当前j所指的字符和next[j]所指的字符不相等那么就让nextval[j]next[j]意味着nextval数组在j索引上的值等于next数组在j索引上的值。例如上述图片中求nextval[2]此时代表模式串第二个字符匹配失败且j等于2其中j指向第二个字符即bnext[j]即next[2]等于1即模式串指针应该改为指向模式串第一个字符即a由于字符a和b不相等所以nextval[2]等于next[2]即nextval[2]1 如果当前j所指的字符和next[j]所指的字符相等那么就让nextval[j]nextval[ next[j] ]nextval[ next[j] ]可以理解为next数组的嵌套当j指针即模式串指针指向的字符匹配失败时需要指向next[j]所指的字符根据题意next[j]所指的字符注定会匹配失败此时就需要把模式串指针改为next[ next[j] ]即nextval[ next[j] ]。例如上述图片中求nextval[3]此时代表模式串第三个字符匹配失败且j等于3其中j指向第三个字符即anext[j]即next[3]等于1即模式串指针应该改为指向模式串第一个字符即a由于字符a和a相等所以nextval[3]等于nextval[ next[3] ]即nextval[3]0其实不难理解因为此时模式串第一个字符a和模式串第三个字符a相等所以当模式串第三个字符匹配失败时那么模式串第一个字符注定会匹配失败所以没必要再对比模式串的第一个字符而是直接考虑模式串第一个字符匹配失败后应该跳到哪个字符进行匹配
练习2 八.next数组优化前后对比 next数组未优化前 模式串指针j指向的第四个字符和主串第四个字符匹配失败 根据next数组模式串指针指向3此时模式串第三个字符和主串第四个字符匹配失败 根据next数组模式串指针指向2此时模式串第二个字符和主串第四个字符匹配失败 根据next数组模式串指针指向1此时模式串第一个字符和主串第四个字符匹配失败 根据next数组模式串指针指向0然后模式串指针和主串指针都自增 匹配后最终查找成功 next数组优化后即nextval数组 模式串指针j指向的第四个字符和主串第四个字符匹配失败 根据next数组模式串指针指向0然后模式串指针和主串指针都自增 匹配后最终查找成功 显然省去了很多不必要的匹配过程。