免费网站空间服务器,做企业官网多少钱,东莞市国外网站建设哪家好,建站63年来第一次闭站 北京站辟谣《LeetCode力扣练习》代码随想录——字符串#xff08;KMP算法学习补充——针对next数组构建的回退步骤进行解释#xff09; 学习路径 代码随想录#xff1a;28. 实现 strStr() CSDN#xff1a;【详解】KMP算法——多图#xff0c;多例子#xff08;c语言#xff09; …《LeetCode力扣练习》代码随想录——字符串KMP算法学习补充——针对next数组构建的回退步骤进行解释 学习路径 代码随想录28. 实现 strStr() CSDN【详解】KMP算法——多图多例子c语言
个人补充 看了以上学习路径后对于KMP有了很深的认识但是两位作者都没有提到一个重要的步骤的原因——构造next数组时 knext[k]; // 向前回退 这一步骤的原因和思想。其实这一步我认为是KMP的精髓所在也是KMP思想的体现所以在理解之后将想法记录下来方便回顾。 个人理解KMP的精髓是不要浪费。已经匹配过的字符串就算遇到不匹配的字符也不要浪费还有利用的空间有点像剥削了… CSDN文章中构造next数组的时候当遇到不匹配的字符时需要向前回退的例子还是过于特殊导致回退一次就可以匹配上这里我又重新构造了新的字符串 分别是求next[6]和next[8]的值。 在构建next数组的时候同时也运用到了KMP算法并不是在搜寻字符串的时候才运用到有点递归的感觉 以第二个next为例当根据之前的最长相等前后缀aba、aba无法直接求得更长的前后缀时b!c否则可以直接构成abac、abac了直接赋值4这时候不能直接放弃还没有榨干之前字符串的价值我们需要跳转 knext[k]; 重点来了为什么要跳转到next[k]呢 aba、aba是两个最长相等前后缀同时他们自己也有自己的最长相等前后缀。并且第一个aba的最长相等前缀和第二个aba的最长相等后缀因为两个字符串是相等的这一点很重要 next[k]还有一层含义阻止当前的最大相等前后缀成长为更长的相等前后缀的字符也就是说这个字符阻止了更长的最大相等字符串的出现 当第一个next[k]匹配失败后我们跳到第二个next[k]组织第一个aba的最长相等前后缀a变得更长的字符b的位置因为上面所说的我要尝试一下第一个aba的前缀阻止字符和第二个aba的后缀当前字符next[7]对应的b能否组成一对最长相等前后缀这样的话aba、aba这一对就没有被浪费还可以利用他们本身的前后缀再次查找并且由于这一对本身没有成功所以他们的字串如果成功的话必然是最大的相等前后缀 总结一下这个回退的操作有点像二分法的感觉第一个前后缀不行就把他们分开看前缀的前缀阻止字符和后缀的后缀新匹配的字符 能否构成新的前后缀如果还不行就在回退再一分为二一直到第一个字符都不行next[k]为-1就代表着一点都不一样赋值为0表示没有了。 构建next数组和字符串匹配都用到了KMP区别是什么呢next是用前缀的前缀去匹配后缀的后缀字符串匹配是前缀不行换前缀的前缀上不行的话再试。两个操作基本一样但是next在于写入值字符串匹配在于移动。 到这里我个人的解释就结束了我是自己把这里想明白之后KMP算法就顿悟了没想明白之前每次回退都十分忐忑。 我的具体实现代码在这里《LeetCode力扣练习》代码随想录——字符串实现 strStr()—Java
