上海企业建站咨询,凡科网站 怎么开支付,做外贸需要什么网站,临近做网站如果时间不够#xff0c;急#xff08;忙#xff09;着应付考试没心思看#xff0c;直接参考#xff08;照抄#xff09;如下套路#xff1a; PART 1#xff1a;关于next [ j ]
PPT#xff1a;P30 根据书上以及视频上给出的思路#xff08;提醒#xff09;#x…如果时间不够急忙着应付考试没心思看直接参考照抄如下套路 PART 1关于next [ j ]
PPTP30 根据书上以及视频上给出的思路提醒我们对于KMP算法拥有了如下的初步第一阶段的了解
书上的内容经过简化和解释说明后的版本 分析模式串t 对于模式串子串t的每个字符 t [ j ] (0≤j≤m-1) 即 j 在字符串最后一个字符前 存在一个整数k(kj)使得 模式串中开头的k个字符(t0…t[ k-1]) 依次与t[ j ]的 前面k个字符t[ j – k ]…t[ j – 1 ]相同 其实就是说
子串里面的第j个字符这个字符他前面的k个字符刚好和子串最前面开头的k个字符一模一样 注 这里我们暂且就给这两串相同的玩意取个名字方便称呼 我们将前者称之为前缀后者称之为后缀 将其图像化可能更加直观 这种属性落实到具体提高比较效率上重点就是当出现了前缀和后缀以后
我们可以把子串前缀移动到后缀的位置主串不变进行下一轮比较
换句话说就是在到下一轮比较时
直接把前缀移动到移动之前后缀所处的位置跳过这中间所有的字符
直接进行这个位置开始的后面的比较 学习过程中遇到的问题很容易踩的坑
按理说这里接下来我们就可以进行顺理成章地归纳关于next [ i ]的公式了比如说至少能理解书上的这一条 但是这里我们很容易就发现一个问题
不是你这个子串不是说是要往后移吗怎么经过了这个公式怎么还越变越小了
k都移动到第j位了j 不得移动到 j j-k位上 这个大概就不对了吧又或者说next [ j ]其实并不代表下一次 j 的位置 然而实际上该问题的出现根源于没有真正的画图和敲代码实践
而该具体问题的核心在于 j 往前指指向字符串前面的第k个字符 并不是说 让 子串的 位序为 j 的 字符移动到 主串的 位序为next [ j ]的位置正下方开始匹配 把后缀移动到之前前缀的位置上来 另外在这个算法案例中此 j next【j】非彼 j前面文字介绍里面的 j
这里的 j 相当于一个功能类似于指针的一个下标 要彻底搞清楚该问题过程的核心和本质我们需要彻底从头开始重新缕一缕这个KMP算法
再整个比较过程中的流程和步骤
实践操作步骤 直接匹配一个一个字符往后匹配直到匹配不上看匹配不上的字符之前的字符有没有能实现前缀后缀一样的有一样的话直接把前缀移动到后缀之前摆放的位置继续匹配这里 j 的执行过程是
从t【0】开始往后面排匹配发现不一样以后i 不变j不一样的前一位
数值变为next [ j ]指向子串内下标为next [ j ] 的字符
再次说明强调 不是说让 子串的 位序为 j 的 字符移动到 主串的 位序为next [ j ]的位置的正下方开始匹配 是主串不动j 指向子串内下标为next [ j ] 的字符 相当于将子串内下标为next [ j ] 的字符向后移动到原来下标为 j 的字符的位置 注意
这里写的所谓的“移动”的说法只是我们为了方便初步理解匹配算法的过程
实际上并不存在什么子串的移动来移动去只有说
操作过程前主串的同一个字符位序为 i 比较的是子串里相对而言靠前面的字符位序为 j
操作后主串的同一个字符位序为 i 比较的是子串里相对而言靠后面的字符位序为 next [ j ] 关于next [ j ]的总结
解决了这么大的一个问题现在我们终于可以可以归纳关于next [ i ]的公式了
1如上面所示如果存在前缀后缀相同的情况我们可以让 j 可移动的类似指针的下标变为 k 指向子串中位序为k的前缀的后面的第一位字符来加速比较
2上面我们都默认下标(位序) j 是从0开始是因为我们的书上写的都是默认为0的情况
实际上下标可以从0开始也可以从1开始比如说PPT、网课里面
但是 对于第一位下标的 next [ j ] 值他们都选择了 比第一个下标小1位第一个下标的前面一位也是我们实际上永远都取不到的一个位置 对于“其他情况”不是第一位但是也没有什么相同的前缀和后缀的 next [ j ] 值 他们都选择了第一个下标位 所以说实际上都可以表面上两个归纳的结果的数值完全不一样
PPT网课上的归纳公式书上的公式实际上他们的数值制定的原理本质都是一样的似非而是
而在这里为了应用的方便我们统一都采用写成书上从0开始的形式
但是我们也要知道
如果我们不想从0开始想要从1开始这也都是可以的只要直接按照PPT上面所执行的公式操作就行 next 代码思路
那么接下来就是我们把准备了那么多的时间的思想转换为代码的时候了 框架
首先我们先把整个KMP匹配算法的大框架搭建好:
int Index_KMP(SString S, SString T, int pos)
{int i pos, j 0;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; //匹配成功,返回子串位置else return false;
}
难题如何写出一个判断子串的前后缀是否相同的语句
另外在这里一开始其实我想写的是不用写什么next【j】直接在代码里通过算法实现倒退到next【j】的功能但是这样反而有点混乱逻辑不清而且到后面其实已经写不下去了 int k 0;while (1){if (T.ch[k] T.ch[j]){k; j--;//然后写一个判断子串的前后缀是否相同的语句//但是这里这样写的话我们可以说要写无穷个判断语句//根本无法实现}} //然后写一个判断子串的前后缀是否相同的语句 //但是这里这样写的话我们可以说要写无穷个判断语句 //根本无法实现 所以如何写出一个判断子串的前后缀是否相同的语句使该算法的核心/重点
下面我们来针对此方面开展工作 首先我们按部就班根据公式 写出如下程序
void Get_next(SString T, int(next)[])
//给你一个子串T教你逐个算出每个位序对应的next[]
//返回所有我们算出的next[]
{int j 0,//从头开始算起k -1;// k 0; //不可以根据公式和算法设计即使是MAX[k]也必须要小于jnext[0] -1;//根据公式while (j T.length - 1)//因为位序从0而非1开始{if (k -1 || T.ch[k] T.ch[j]){}}
}然而写到具体如何一个一个判断匹配把比较前缀后缀的思想实现成代码的时候又卡壳卡住了
对此我们的解决方法是 多画图一步一步、一格一格算不用着急慢慢来 画出步骤图如下 在这个过程中我们很容易就感受到 其实如果上一步进行匹配运算结果为真的话 下一轮其实我们只需要比较上一轮比较的两个串的后面的一个字符就可以直接判定结果 下一轮的next 【j】是不是上一轮加一 有人说你这TM不是废话吗但是这句废话在我们这里的程序设计中含有至关重要的意义
事实上根据上面这句废话我们可以画出我们在采用这种方法的流程图
如下 根据上述流程图我们不难得到 if情况新字符匹配
1实现前面所说的
实现一个一个判断匹配把比较前缀后缀的思想实现成代码的操作
至少这里我们可以通过废话 其实如果上一步进行匹配运算结果为真的话 下一轮其实我们只需要比较上一轮比较的两个串的后面的一个字符就可以直接判定结果 下一轮的next 【j】是不是上一轮加一 以及流程图写出 if 判断语句后面的表达式
思考逻辑流程
第一次给next【j】赋值的时候 我们要意识到next【0】是在一开始我们就已经给了他初值的 也就是说第一个被赋值的是next【1】
此时系统给的条件 j 0, k -1; 而我们要写入的是next【1】 重新参考步骤图我们知道
给next【1】赋值时k 0 j 1
更何况后面每一步我们都要进行自增然后再比较的操作
所以自然的 j; k; 的操作是不可少的 然后我们要考虑的就是赋值和自增操作的前后顺序安排问题了
再对应着步骤图一个一个看
next [ 1 ] k 0 j 1next [ 1 ] 0next [ 2 ] k 1 j 2 一样next [ 2 ] 1 不一样next [ 2 ] 0 next [ 3 ] k 2 j 3 一样next [ 3 ] 2 不一样next [ 3 ] 1或0
我们可以看到
如果后面的那一个新的字符匹配结果为真
则 next [ j ] 的值就为新的和上一轮不一样的k的值新的值其实这里也就是自增过以后得的值
匹配结果为假那是else情况里面的东西我们先不管他
所以从上述操作我们大概就可以判断出来如果后面的那一个新的字符匹配结果为真
那么就先自增然后赋值next [ j ] 新的k else情况新字符不匹配
现在我们回过头去看看流程图研究匹配结果为假的情况
步骤
1我们会可以发现无一例外他们进行的操作都是去执行少一位的前缀和后缀的比较匹配的算法操作
当然了很多人会说这又是一句废话你TM介绍算法的基本原理的时候里面TM不就写着吗
2既然如此他执行的还是这个比较的操作比较的操作流程必须由前面的 if 语句执行
一方面我不可能去再重复写一遍这个比较
另一方面如果一直这样写下去的话后面就变成了无穷无尽的循环了
所以说到这一步我们需要思考的
是怎么让前缀和后缀这两个东西倒回退回去而不是在 else 里面写比较的语句
3在参考过课本上的思路以后我们意识到
其实回头去找前缀后缀里面最长的、能相等的两个串本质上和我们比较子串和主串本质上其实没什么区别
也就是说在这里我们可以用KMP算法直接加速这一比较的过程
更巧的是他前面其实已经给我们算好了 j 前面所有的 next [ j ]
当然在这我写是这么写但是总感觉要完整这个过程好像还缺点什么不够确定就是这样说不出来缺了什么东西
总的来说到了这一步我们可以用KMP算法在 else 语句后面写 k next[k]; 也可以老老实实的就用BF算法 k--; 是 k-- 吗我好像不确定欢迎大家指正
代码实现见下一节
