山西网站建设排名,网站运营推广公司,公众平台网站开发哪家好,磁力猫最好磁力搜索引擎本文具体思路参考#xff1a; #xff08;最后证明#xff0c;该教材/网课实际上是最有效的#xff09;
DS第四章【3】KMP1_哔哩哔哩_bilibili 中间走的一些弯路的教材#xff1a;
第06周05--第4章串、数组和广义表5-4.3串的操作--串的匹配算法2--KMP算法_哔哩哔哩_bi…本文具体思路参考 最后证明该教材/网课实际上是最有效的
DS第四章【3】KMP1_哔哩哔哩_bilibili 中间走的一些弯路的教材
第06周05--第4章串、数组和广义表5-4.3串的操作--串的匹配算法2--KMP算法_哔哩哔哩_bilibili
课本
走弯路过程详见
数据结构与算法基础王卓16KMP算法个人学习历程
虽然里面学的过程用的很多的是生硬的笨方法但是里面遇到的问题和踩的坑还是值得一看来更深理解KMP算法的 PART 1关于next [ j ]
PPTP30 根据DS第四章【3】KMP1_哔哩哔哩_bilibili 需求
返回子串和主串匹配时候的位置 思想
把上面的主串也就是箭头左边的前面的那一部分当成箭头左边的子串的一个分身
注比较到不匹配时箭头指针指向不匹配的字符
他们之间公共的部分 要么是完全对其时候的全部 要么是下面的子串移动到其主串公共后缀的位置的时候 其他上下两个串摆放的位置都不可能产生我们想要的公共的部分 其实分析这个问题的时候我们就已经不用去看主串的位置和情况了因为其实我们已经知道
在匹配不上的前面箭头左边子串和主串都是一样的所以其实只要看子串就行了
所以我们只需要找出前面箭头左边的公共前后缀
然后往前右移动子串让他的前缀移动到原来后缀的位置
就可以解决这个问题往下比较了 核心
直接把前缀移动到移动之前后缀所处的位置跳过这中间所有的字符 好了现在我们思路有了接下来
具体落实怎么移动
移动目的找到主串子串完全匹配的位置 如果发生的是主串和子串比较的字符匹配的情况我觉得我们根本不用讨论 现在比较的这一位匹配那就比较下一位 如果一路匹配下去一直都是能匹配的上的话那就返回结果 子串放在第一格可以和主串匹配上 就行了 所以我们需要讨论解决的是当每一位发生了不匹配的操作时我们怎么相对应的处理
另外我们这里不仅要知道下一步该具体怎么移动还需要思考
如何用指针实现进一步的比较所有的探究、思路都是为了写出程序服务 现在我们知道了当每一步每一种情况我们应该怎么进行操作
根据上图我们就得到了下一步如何操作把子串的指针移动到哪个位置的操作的
公式
字符串从位序 1 开始存储时
PPT网课上的归纳公式字符串从位序 0 开始存储时
书上的公式以上都是怎么进行移动的公式、思路、理论接下来我们是要写代码的
先不写KMP算法代码我们先写求每一位匹配不上情况的next把子串的指针移动到哪个位序
当我们一个一个排匹配下去显然当我们比较两个字符的时候
这个字符前面的所有字符都应该是匹配的如果不匹配我们就移动子串的指针位置重新从头开始比较这个字符前面的所有字符的 next 数组的信息我们都是可以知道的
所以
现在我们每往下走一步面临的问题就是 主串和子串比较的字符匹配【if1】讨论无意义 if (k -1 || T.ch[k] T.ch[j]){j;k;next[j] k;}
所以讨论不匹配时【if0】怎么处理我们面临的情况 再次强调 我们要把思路转变一下 不是说我们求的是next【j】 而是我们求的是next【j1】 我们需要的是从过去推出未来而不是说 未来是什么我不知道然后我再去猜过去式这种情况还是那种情况 那种的情况(不等)又只知道一半 只知道最后面一个字符不匹配在前面的就不知道了 这样研究的话那还不如具象化的研究 不要让自己走向未知的方向。走进越来越未知的方向 从已知走向未知让未知走向已知 把上面的这个模式串子串分身【位序 j - k 到 k - 1 】看成主串 把下面的这个模式串子串分身【位序 0 到 k - 1 】看成子串 于是该问题转化为 主串与模式串最后一个字符不匹配 然后同样的比较比较什么 子串里有没有公共前后缀 确定后面该移到哪个位置 特别注意
不要遗漏已知条件这个条件和之前主串子串匹配同样类似/相似 在我们这个不匹配的字符前面所有的字符全部都匹配 现在我们回到解决问题的
核心子串模式串该移到哪个位置 kmp算法 同样的找到这里子串【0到k】前面的公共前后缀 然后把前缀移动到后缀的位置看看新的前缀后面的字符能不能和第 j 位匹配得上 操作上面的图已经写了
子串指针移动到【k 1】位序 elsek next[k]; 如果我们一定想用bf算法证明我们真的熟练掌握了这种思想 如果我们用bf算法也就是说一格一格往右边移 主串位置不变子串一格一格往右边移动一次一次比较 直到匹配成功到 前缀后缀一样 乃至子串和主串一样为止 所以我们要进行的操作就是
主串指针不变子串指针不断指向前面一个字符下一次比较
实际操作就是k-- elsek--; 再次强调
匹配“下一位字符”之前我们不用担心
他这个“下一位字符”和主串前面部分的字符能否匹配得上
这个问题的
即使这个“下一位字符”不匹配在我们这个不匹配的字符前面所有的字符全部都匹配 疑问
为什么不从中间开始匹配
如果中间有和后缀一样的但是开头没有呢
我们要求必须从开头开始算前缀是不是容易漏掉一些可能的正确答案呢
答案 如果中间有但是开头不行那最后子串中间的字符是匹配了但是中间的 前面的那部分字符终究还是不匹配那迟早要完蛋终究是失败的 另外
为了强调和体现我们“求的是next【j1】”的思想和精神我们不妨把【if1】处的代码更新为虽然我后面最后的答案里面不是这么写的 if (k -1 || T.ch[k] T.ch[j]){next[j 1] k 1;j;k;} 答案
#includeiostream
using namespace std;
#includestdlib.h//存放exit
#includemath.h//OVERFLOW,exittypedef int Status;
#define MAXLEN 255struct SString//Sequence String
{char ch[MAXLEN 1]; //存储串的一维数组int length; //串的当前长度长度
};void Get_next(SString T, int *next)
//给你一个子串T教你逐个算出每个位序对应的next[]
{int j 0,//从头开始算起k -1;next[0] -1;//根据公式while (j T.length - 1)//因为位序从0而非1开始{if (k -1 || T.ch[k] T.ch[j]){j;k;next[j] k;}elsek next[k];}
}int Index_KMP(SString S, SString T, int pos)
{int next[MAXLEN];Get_next(T, next);int i pos, j 1;while (i S.length j T.length){if (S.ch[i] T.ch[j]){i; j;}//主串和子串依次匹配下一个字符elsej next[j];}if (j T.length)return i - T.length; //匹配成功elsereturn 0;
}int main()
{}
