408代码题会出kmp算法吗

这里是代码孙小璐，我是程序员 carl， 最近呢，在公众号里分享了几篇 kmp 算法的文章，和很多小伙伴们呢交流之后，发现大家在学习 kmp 算法的时候呢，都会遇到这样或那样的疑问， 那么呢，呃，我来啊，做一期视频，把 kmp 算法呢从头到尾讲一讲啊，希望可以解决大家心中对 kmp 算法的疑惑。 好了，那我们首先那就讲一下这个 camp 算法这个名字。 camp 算法的名字呢，没有什么高深的含义啊，就是发明这个算法的三位学者的开头字母啊，就组成了 camp 算法。 那么 kmp 算法它能解决什么样的问题呢？ kmp 算法解决的就是字符串匹配的问题啊。举一个非常经典的例子，给出一个文本串， a a b a a b a a f， 那再给出一个模式串， a a b a a f， 嗯，这里好，可以应该匹配上啊，好， 那我们要求在这个文本串里呢，在这个文本串里是否出现过这个模式串啊？这是 kmp 算法解决的一个经典性的一个问题， 那么正常我们一个呃，这一个暴力的解法是什么样的？那指定是两层啊，两层负循环一个，先便利一遍他啊，第二层工序，第二层负循环呢，是便利模式串， 然后呢挨个去匹配啊，那我们一开始呢，这去匹配的时候， a a a a b b a a a a b f， 这里呢就不匹配了，那整体呢，将这个模式串啊， 再向后移移位啊，继续匹配，然后再匹配不上，向后移移位，直到啊移动到 a a b a a f， 直到这个模式串呢移动到这里啊，他才能和这个文本串呢，正好匹配上，所以说呢，才找到了这个文本串里边出现过这个模式串， 那么暴力匹配的这个时间复杂度呢，很明显是大 om 乘 n 的， 那这里呢， n 呢就是文本串的长度， m 呢就是模式串的长度啊，那么我们来看一下，使用 kmp 算法是如何解决这个匹配的问题呢？ 我们在这里 a a a a b b a a a a b f 在这里不匹配的时候呢， k m b 算法不是要从头去移动它，而是在这里 f 和 b 不匹配之后，它会跳到这里， 它会跳到之前匹配过的内容啊，那之前匹配过 a a 嘛，所以说它会跳到 b 这里啊，然后继续匹配，那此时 b b 匹配， a a 匹配， a， a 匹配， f 和 f 匹配，那么我们就在文本串里边找到了一段子串，完全可以匹配这个模式串，这个呢就是 camp 算法，那么我们就来说一下 camp 算法呢，它是 是如何找到的这个 b 呢？是吧，他如何能知道我们之前匹配过哪些，并且跳到啊那个已经匹配过的内容的后面继续开始匹配呢？这里就要说到一个非常重要的一个表，就叫做前缀表， 那么为什么要用前缀表呢？那 camp 算法为什么不用哈西表啊，用叉叉表啊，必须要用前缀表呢？ 那前置表它有一个什么样的一个特性啊，能让我们去找到之前已经匹配过的内容呢？我们来看一下，在这里我们打 f 的时候跳到了 b 这里，那之前，哼， f 前面的这个子串 aabaa， 他的后缀是不是 aa 呀？他的前缀是不是 aa 呀，那么我们之前在 f 这里不匹配了，那在这里我们找到 f 的前面， 他的这个子串的一个后缀是 aa， 我们就找到与这个后缀相等的前缀的后面重新开始匹配。那与其相等前缀的后面是什么呀？就是 b 嘛，我要从 b 这再重新开始匹配， 所以说那这里我们要求的其实是什么呢？我们要知道啊，一个字符串里边他的最长相等前后缀。这样呢，我们就在遇到不匹配的位置的时候呢，我们就找前面这个子串，他的 最长相等前后缀是多少？那在这里他这很明显，这个他最长相等前后缀呢？他这个是二，他会跳到下标为二的位置，跳到 b 的这里， 正是因为这个前缀表呢有这个特性，所以说我们要选择前缀表来解决这个问题。 那刚才说的这个匹配流程呢？大家可能听着有一点懵，那接下来我们再来仔细说一下这个前缀表究竟是怎么求的，以及再说一下我们如何用这个前缀表完成这个匹配的过程。 好了，那么我们来说一下这个前缀表。说到前缀表呢，我们就要介绍另一个概念，什么是前缀，什么又是后缀呢？啊？我们 拿这个模式串来举例，这个 a a b a a f， 在这个字符串里边，它的前缀，这个字符串的前缀是哪些呢？前缀是包含首字母， 不包含伪字母的，所有子串都称为前缀。那么我们这个模式串的在这边，我们看他的前缀都有哪些？ a a a a a b a a b a a a b a a 这五个都是前缀，但是 a a b a a b a a f 就不是前缀，我们不包含伪字母， 那说完前缀呢，我们再说一下什么是后缀， 什么是后缀呢？后缀是只包含尾字母，不包含首字母的所有子串。 在这里边都有哪些后缀？ f 是后缀， a f 后缀 a a f 是后缀， b a a f 也是后缀 a b a a f 也是后缀 a a b a a f 不是后缀， 因为不可以包含首字母。这样呢，我们就知道了什么是前缀，什么是后缀。接下来呢，我们就要求最长 相等前后缀，这里要强调一下，我们要求的是最长最长相等的前缀和后缀的长度。 网上很多文章呢，就在啊，网上很多文章在介绍 camp 算法的时候呢，都说是最长公共前后缀啊，或者是什么公共前后缀，其实呢，我认为公共两个字是不准确的，我们要求的是最长相等，要的是相等的前后缀。 那么我们来分析一下这个最长相等的前后缀，我们来看一下这个模式，串是 a a b af， 那么我们来逐个来分析一下，他的这个开头的这个子串，他的最长相等前后缀都是多少呢？首先来看 aa 的话，他的最长相等前后缀是多少呢？ a 的话，其实理论上它是没有前缀，也没有后缀，因为它是首字母记尾字母嘛，那么它的相同前后缀的话就是零，那 a a 呢？ a a 的话， 前缀 a， 后缀 a， 所以说相等的前后缀长度是一 a a b， 那这里呢？因为后缀有 b 嘛，所以说这个找不到与其相等的前缀长度是零 a a b a， 那 这里 a 和 a， 那只有这一个相等的前后缀，所以说长度是一 a a b a a， 那这里边有个 a， 有个 a 啊，有个 a a， 有个 a a， 那长度是二，那最后是 a a b a a f， 在这里我们找不到相等的前后缀，所以说呢，最长的相等前后缀是零，在这里边我们就得到了一个序列， 是零一零一二零，这个呢其实就是我们的前缀表，就是我们这个字，我们这个模式串的前缀表零一零 一二六，那么我们得到了这个前缀表，我们如何用这个前缀表来 进行匹配呢？我们来看一下 减脂表，是零一零一二零， 我们在这里呢，还是我们一开始匹配时候，这是 a a a b b a a a a b f， 在这里我们 找到了啊，这个充足的位置哈，不匹配了，不匹配了之后，我们要找啊，他的前面这个子串，在前面的这个子串，他的最长相等前后缀啊，是多少？ 最长枪头前后缀记录就在记录在这里，这是二，是吧？那这个二意味着什么？ 意味着这里有一个后缀 a a， 前面也有一个与其相等的前缀 a a， 我们在这个后缀的后面 啊，不匹配了，是吧？冲突了，那我们我们就要找与其相等的前缀的后面，继续开始匹配，那与其相等前缀的后面，那那下标是多少呢？七十， 就是这个字符串 aabaa， 他的最长相等前后缀的长度啊，那就是我们要继续要啊，继续去匹配的位置，那也就是指向了这个 b， 那么可以看一下这次引线表零一 二三四五，我们这个最长向的前后缀是二吗？那么我们就要跳到这下标为二的位置继续开始匹配，为什么 正好就要跳到二的位置呢？因为二他表示的是相等前后缀的长度是吧，那么我们就要我们要跳到前缀的后面，是吧，那前缀的后面，他的下标不就正好是前缀的长度吗？因为 所以是从零开始的，所以说我们跳到了二的这个位置，所以说是从 b 这里重新开始匹配，往后 b 这里继续匹配 aa f， 最终找到了 aab aaf。 那这样我们就用我们的这个前缀表啊，完成了我们这个匹配的过程。 那么我们再说一下，呃很多就是 camp 算法的这具体代码实现里边呢，都会提到一个 nice 的数组啊，有的呢也会用 perfects， 其实呢啊都可以啊，用 pro face 呢，就是说明啊，这个数字代表的就是这个前缀表啊。嗯用 nice 它呢？ 其实呢他放的也是前缀表，那只不过是有的时候他会对这个前缀表呢进行某些调整，那其实用不是 face， 用 nice 都是可以的。那我们这里边呃统一称呼这个数组为 nice 数组吧。 为什么啊他们会叫 nice 数组呢啊？可能就是因为我们在遇见冲突的地方之后，我们这个 nice 的数组告诉我们要回退到哪里啊，要回退到下一个位置，所以说就叫 nice。 那很多呢？呃实现 can， 呃，很多就是，呃具体实现 camp 算法的过程中呢？呃会把这个前缀表呢做一个 啊又移的操作，或者是做一个统一减一的操作啊，效果其实都是一样的，都是初始位置变成负一，后面的话呢，要不就整体又移，要不就是整体减一，那你看我们的这个呢，统一减一之后就变成了负一零 负一零一负一啊，就变成这个了，这个的话呢 啊，一般啊，有一种实现 kmp 代码的风格，就是拿这个数组啊去做匹配，那他统一减一了之后，他去匹配的时候呢，他还会把这个一加回来。 有的呢是说整体右移啊，往开其实位置是负一，这是其实。呃，这个具体啊，是右 就一样还是从一减一啊，是涉及到看一批算法的一个具体的实现，其实呢，不涉及到具体原理，这个前缀表我们就用这个前缀表，原封不动的啊，作为我们的 nice 数组，依然可以完成看一批算法的工作， 所以说这是两种啊，不同的实现啊，同学们呢，其实不用太纠结于这一点。 呃，我们这一期视频呢，先就讲解这些啊，把 kmp 算法的整个原理性的东西啊，我们介绍了 kmp 算法， kmp 算法能解决哪些问题， 以及 kmp 算法他为什么就可以啊，就是匹配失败之后可以跳到之前匹配的位置。我们啊引出了这个前缀表，然后我们说一下为什么一定要用前缀表， 为什么不用哈西表啊，不用叉叉表，一定要用前缀表，接着我们介绍一下前缀表的特性以及如何啊，去求取这个前缀表，接着呢，我们用这个前缀表呢，完成了一次匹配的操作。最后我们又说一下，就是具体在实验 kmp 算法的过程中呢， 有的呢会做统一减一，有的呢是右移，其实不涉及到 knp 算法原理性的东西，只不过是实践上啊，实现上方法不同而已， 那么我们这里呢就啊对 kmp 算法理论性的东西呢就介绍到这里了 啊，具体的实现呢，我们可以在下期视频里边再和大家啊详细的讲解一下，好了，谢谢大家的观看。

计算机考研专业课四零八，每次考科目如何开窍？在战斗中学会战斗。计算机方向属于功课，公科和理科的区别就是它是属于实践的一个月，这个如果你想开窍，必须要亲自动手。所以有一句话适合于所有的工科专业，叫做在战斗中学会战斗。就是边学边用边用边学嘛。下面呢，我们说一下具体的四零八四本数据结构是理解 a d t， 这科是属于计算机的基础科目，前面很多视频我也强调了 a d t 很重要，比如什么是对列，什么是战，什么是数，他们的 a d t 是什么，为什么要引用这些东西， a d t 就能解释这些， 他就在违章的开篇跟结尾嘛，然后代码你你也得肯定写，因为考试也会考点嘛。操作系统是用的那个字，那个字跟温度有很多不一样的地方，这 使用体验的差别啊，主要是那个字是偏命运行的操作和一切接文件，所以他特别适合操作系统。变学为荣。这个二零二一年的考研四零八里边有个题目是关于训练机的，这个题目其实懂的人都懂，做文都都懂， 不懂背景就是学生用虚拟机装那个字，这有一个很明显的信号，各位能看出来吧，拎那次他开元就商业约束很小，不会轻易被某些国家使办的。你在结合当下的这个国际环境啊，你自己琢磨琢磨这个，这里边值得挽回的事情其实很多的。所以我预测啊，拎的是在今后的计算机考研里边，不管是笔试还是复试， 嗯，都会有气氛，就算你组成圈里就传电脑记住的知识砸着伞。如果要深究的话，得从数字电路的各种门学起。与其说他是难啊，不如说他是麻烦，特别是对于跨跑的人。这个你能怎么抬脚入门呢？就把自己的即将你拆开， 看看内存、 cpu， 显卡都长什么样，比如说某个游戏你带不动啊。嗯，你认真想想，就认真的想想，是 cpu 不行还是显卡不行，还是内存不行。为什么不行？要不要换？你要换？换成什么样的配置？举个反面例子啊，就有的人动不动就说我的电脑内存不足的，没地方存 见了。这个显然是连内存的硬盘都没有分清啊。你要是脑补不出来自己电脑里边长什么样，你还要想学好剧组其实是很累的。这个，所以有心的各位啊，你就藏个电脑试试吧，你没钱你可以拆个对象去看看。既往是层次， 网络是分层的对吧？从物理层到应用层，你要么从下向上，要么自定向下。最近流行那本书叫做指定向下，就很多很多看过人都说好啊。所以就结合了层次学吗？ 除了四零八，有的学校有会有自主命题，考其他科目，深入了解计算机系统这本书写的是非常好的，你怎么看下？人家书里边其实也直接写了就是定性词环境的 c 语言变成人家书里怎么写，你就怎么用它其实适合啊，计算机专业的第一本书，作为计算机的捣乱去学 这本书啊。你最好大一就跟这四亿元一块学，你看完这本书再去学四年班，我其实超推荐这个顺序，你入门大一的话可以试试四亿元，这个得直接动手，轻松几代，玩 机会的话，你就在另一所环境之前你用了 dcc 的 gdp。 c 加加这个也是动手啊，这门语言啊，比较复杂，就大多数本科学校也就交到面向对象，就意思意思就完了。我个人觉得啊， c 加加你如果真的很有诚意的想学下去， 是结合机制和力扣的去学，因为你刷四块，你总是要用 s 条吗？对吧。以上呢，就是计算机专业课各门的一句话开窍总结。其实仔细想想啊，真的是在战斗中学会战斗，公开都是这样的希望呢。如果你做题没有思路，做题没有思路的时候啊，这个视频呢，得启发。

这里是代码孙小璐，我是程序员卡尔。上期视频呢，我们讲了 k n p 算法的理论基础，但是没有涉及到具体的代码实现，那么这一期视频我们就来讲一下求前缀表的具体代码应该怎么写。 我们在上一期视频呢，提到了一个模式串是 a a b a a f， 与其对应的前缀表呢是零一零一二零。 那么呢，我们也说到了在具体的写代码的过程中呢，有的呢，用 nice 的数组来表示这个潜水表，有的呢用 perfect 啊来表示这个潜水表，那我习惯于用 nice 啊来表示这个潜水表，所以说在后面的讲解中呢，我会啊称之为 nice 数组。 那么在求这个 nice 数组的过程中呢，其实啊，不同的人写法还是很不一样的，大家可以看到网上的一些视频啊，文章啊，发现 这个是前缀表，那有的呢，会把这个前缀表整体右移变成零一零一二，然后初始位置变成负一啊，拿这个作为 nice 数组，那有的实现呢是把这个前缀表呢 整体减一负一零负一零一负一啊，把它整体减一啊，拿这个作为 nice 数组， 那有的呢，就直接原封不动的拿这个前缀表作为 nice 数组那，呃，如果刚开始学 kmp 算法的同学啊，看到了就是不同呃，不同人讲解的时候呢啊， 雄奈词数组各种方式，可能会有点疑惑是吧，那么其实呢啊，这些实现的方式呢，都是可以的， 只不过是在比较上的原则有出入。那么在后面啊，那么我会举一个例子啊，举个例子呢，大家可能理解的就 就会更加啊容易一些，我们在上集视频里边那一个文本串是 a a b a a b a a f， 那么我们在这个模式串和文本串进行比较的时候呢，是在 f 这个位置发生了冲突，是吧？因为前面 a a a a b b a a a a 都是 相等的吗？就在 f 这里和 b 啊它是不相等的，那么在这里发生了冲突之后，我们是看 f 的前一位啊，是看他的前一位的这个前缀表所对应的值是多少，这个值呢，就 是对应着下标二的位置，然后我们就跳到了这个 b 的位置，是吧？ 那么他们有的实现呢，是把这个奈斯数啊，是把这个前缀表呢整体又移往后，初始复初始为负一啊，得到这个奈斯数组，他们在遇见冲突的时候呢，是直接比较 f 所对应的这个 啊，所谓的 next 数组的值啊，是二，然后呢就跳到了 b 的位置啊， 那此时大家是不是发现这两种奈斯数组的数值，只不过是表示我们在遇见冲突的时候呢，我们去找的方式不一样，那如果就拿这个前缀表作为奈斯数组，遇见冲突了，我们就找这个冲突的前 前一位所对应的下标，那么如果要是把这前缀表又移了，出水为负一，那就是遇见冲突了之后，我们就找冲突的这个位置啊，所对应的下标也依然找到了 b 的这个地方。 那么有的实线呢，是把这前置表统一，他都减一了啊，那减一之后，其实呢，我们遇见冲突呢，还是看他的前一位，只不过是他统一减一之后呢， 他的前一位，他会把这个一加上来，这个一加上一变成二，依然还是啊，会回退到这个 b 的位置， 此时呢大家就应该知道了，那么这么多啊，求 nice 数组的方式，其实最终目标都是一样的，遇见了冲突的位置，我们要向前回退 啊，这是奈斯数组的核心所在，至于具体实现吗？不同人的实现是有不同的方法，那么我这里介绍的呢，就先，呃，就拿这个前缀表作为我们的奈斯数组，那我们来看具体代码的时候我们应该怎么写呢？ 首先求这个 nice 数组呢，我们会定义一个函数啊， 呃，我这里写的代码呢，大家可以理解为一种伪代码啊，但是我会尽量的让他表达出他真正 的含义。大家如果想看具体的实现代码的话，可以在我的呃公众号里代码随选路后台回复 k m p 就可以获取啊。本期视频呃所讲解的具体可以运行的代码， 呃，这个函数名就叫做 get next， 那参数应该是什么呢？首先我们要传入一个 nice 数组吧，是吧，我们要对这个 nice 数组进行呃一次，呃 啊，我们要对这个 nice 数组给他进行复值啊，然后呢把这个模式串 s 啊传入进来， 这样呢我们定义完这个函数，定义完这个函数，我们要明确，那求那 s 数组我们有几个步骤，首先呢是初始化， 初始化的话就是初始化我们的 nice 的数组啊，以及初始化我们的函数里的各个变量。然后呢是处理啊，前后前后缀不相同的情况， 然后呢是处理前后缀相同的情况， 最后呢是更新 nice 数组的值，一共呢就这四步，那我们按照这四步来看一下代码音 应该怎么写？说到初始化那，呃，我们在求那次数组的时候呢，都涉及到了一个指针 i， 一个指针接，是吧？那这个 i 和接啊，究竟是什么含义呢？ 我们在代码里边明确 i 和接是什么含义，那接呢，它是指向啊，前缀末尾位置， 那 i 呢，是指向后缀末尾位置 啊，这样呢，是我的一个写代码的一个习惯啊，但，嗯，大多数啊， kmp 的代码呢，其实 也是遵循着这个规则的啊。那么我们进入到这个函数，我们进行一个初始化，接呢，它是指向前缀末尾，其实呢，接它不仅仅是指向了前缀末尾，接它还代表着 i， 这个 i 之前包括 i 之前的此串的最长相等。前后缀的长度其实也是接，接呢，同时它也表示前缀的末尾。 那么我们来看一下这个接的初始化应该是多少呢？那接初始化应该是零吧，是吧？前缀一开始是从最开始的位置开始啊，那么我们的 nice 数组是不是也要进行初始化啊？ nice 数组的话 零的位置，那我们在零的位置，我们应该回退到哪里呢？那很明显也是回退到零吧。啊，那 初始位置也是零，这样呢，我们就完成了初始化。哎，那大家可能疑惑了，那哎，怎么有初始化呢？是吧？那哎的初始化呢，其实就是进入到我们的一个循环便利的一个过程了。 i 出水化，应该出水化多少呢？这里接出水化为零，因为接是前缀的末尾，那么我们在这里要比较前缀和后缀啊，所对应字符是否相等，那 i 呢，就应该是从一开始 这样呢， i 和接才能进行比较嘛，是吧，所以说呢， i 等于一 i 小于 s 点 size， i 加加，这样呢，我们就初始化了 i， 同时呢，定义好了我们的一个循环的一个条件， 然后呢，我们就要进行处理啊，前后缀不相同的情况，那么前后缀不相同的情况是什么样子呢？ 接指向了这里， i 指向了这里，那接所代表的位置是 a， i 所代表的位置是 b， 那此时 i 接不相等是吧， 那此时呢，是 s i 不等于 s j， 那么在不相等的时候，也就是 前缀末尾和后缀末尾不匹配的位，不匹配的时候呢，那么这个肩呢，就应该是向前回退，是吧？ 那接向前回退，接怎么回退呢？接要看他的前一位的 nice 数组的值啊，所对应的值就是他要回退的下标，那他就要回退到零的这个位置，为什么要看这个接的前一位呢？ 因为我们在求这个前缀表的时候，遇见冲突也是看前一位啊，这个值， 这个啊，前缀表里对应的值，往后我们才知道跳到哪里啊，那么这个遇见冲突，看前一位呢，其实就是一个不变量，那这个循环 不变量呢？其实大家在写代码的时候呢，会经常涉及到，那么我们遇见冲突呢，但前一位呢，他冲突的值就是我们在这个写这个代码中呢，所要坚持的不变量。当然了，你遇见冲突， 遇见冲突呢，你想看冲突的位置，这个位置啊，你想跳到就是需要回退的位置也是可以的，那这种实线呢，就是刚刚说的，把这个前缀表呢整体右移，然后初始位置变成负一，你就可以 啊，冲突的位置呢，你就找冲突位置所对应的啊 nice 数组的值，然后跳到啊应该回退的位置了。所以说这里呢，就是不同的代码实现，那我们的代码实现里呢，是遇见冲突呢，就看 前一位，所以在这里 i 和接不匹配的时候呢，我们接也是要看前一位所对应的啊，下边的位置才跳过去啊，回退过去。那么接呢，就应该是向 它的前一位所对应的 nice 数组的这个值啊，回退回去。 那么我们回退到什么时候是头呢？很明显，我们这个初始位置是零，那在这里呢，我们用到了 j 减一，因为我们要看前一位嘛，所以说我们在判断的时候呢，要让 j 是大于 零的啊，因为接到零的时候呢，就已经回到了初始位置，就没有必要再去回退了。你看 nice 数组，零的位置是等于零，如果在这再进行回退的话，那相当于这里会出现一个负一了吗？相当于是对数组的下标有负数的操作了，那样会就会造成了越界吗？ 那么这样呢，我们要保证 g a 是大于零的，那这是一个， 这是一个，他俩要同时满足这个条件，那此时呢，我们这里很多同学呢，在写 kmp 代码的时候呢，在这里会写成 is， 这个就是出错的根源所在。我们在回退的过程中，是回退一步就完事的吗？其实他遇见充足的时候，那这个接向前回退是一个连续 去回退的过程，所以这里呢不能写成 if， 而是 where will 接大于零，同时啊， s i 不等于 s 接，那么接呢，就找它前一位啊，需要回退的位置进行回退， 这样呢，我们就处理了前后缀不相同的情况，接下来呢，我们再来看一下前后缀相同的情况， 前后缀相同的情况呢，就是 if s i 等于等于 s j 是吧？那 前缀相同的情况是什么样的？我们再来看一下，就从这个起始位置就可以了，起始位置呢，尖是在这里，哎，是在这里，那我们把这个前缀表这些数值呢，我们给他擦掉， 哼，此时 i 和接所对应的字符是不是相等啊？那相等之后应该怎么操作呢？ 相等之后接，此时是零，接就应该做加一的操作，因为接他不仅代表着前缀末尾的位置，他也代表着，哎，包括，哎之前这个子串的最长相等前后缀的长， 那此时这个 i 的位置包括 i 这个位置之前是不是这个子串 aa 啊？那我们求取了他的最长相等前后缀是一了，不是零了，那接就应该是加加啊，接接呢就从零变成一的位置， 那这样呢，我们让接加加，接加加之后呢，接加加之后我们就要更新我们的 nice 数组单词了，因为我们在这里 nice 数组是不是还是空的呀？ 那此时 nice 接啊， nice 的 i 所对应的这个 nice 数组的值啊，这个数值应该是多少呢？就是我们接的值是一，我们的接已经加加了吗？ 更新耐克数组的值， 这样我们就把这个 nice 数组的这个值呢就给填充上了。此时呢，那我们在这里就前缀和后缀都匹配上了，匹配上之后呢， i 也要向后走一位，那 i 怎么走一位呢？比方啊，我们这是在一个， 我们这是在一个后循环里，那，哎，在下一轮循环里边，自然他就加加了吗？哎，就走到了这个位置， 然后呢，接也接夹接就走到了这个位置，此时呢，我们就把这四种情况都处理好了，初始化前后缀，不相同的情况，前后 对相同的情况，最后更新 nice 数组的值，那整个这个 gets nice 的这个函数我们就写完了，那我们来看一下这个函数它的运行过程如何是把这个 nice 数组啊给填充上的呢？我们来看一下， 此时 i 和接所对应的位置是不是不相同啊？不相同，前后缀不匹配，那么接要找他的前一位所对应的下标，那接着前一位所对应下标是不是零啊？他又回退回来 在这里吗？接找他的前一位回退回来，回退回来进行比较，依然不想等，依然不想等的话，我们的接呢，他的条件是大于零，因为接回到零的位置已经回到了起始位置了吧，就 没法再再向前回退了。那么此时我们更新 nice 数组合值，那就是此，这个位置就是零，那我们的 nice i 呢，就等于接啊，往后这个位置呢，就更新零，它代表的就是他 i， 包括 i 之前这个子串的最长相等。前后缀是零啊，也就是我们接的值，那么继续 i 向后移位， 此时 a 和接对应的这个字，呃，对应的字符啊，是不是都是 a 呀？那此时他们就相等了，相等之后呢，接就应该加加，接加加之后我们更新我们的 nice 数组的值， 更新我们 nice 数字值，此时就是咿呀啊，接加加向前走一位， 你看我们的这个子串的最长相等的前后缀的长度就是一吗？是吧，这个一也就是我们这个接的值， 然后呢，这个 i 呢？继续向后，下一轮循环 i 继续向后走一位， i 继续向后走一位，之后，那 i 和 j 进行比较，同样还是啊，都是字符 a 嘛，那 j 继续加，加， j 继续加，加往后更新 nice 数组为值，这里呢就是二，是吧？那 j 呢？加加到了这里， i 呢？ 给大家到这里， 这里 i 和 j 在进行比较的时候是不是不相等啊？啊？ 就是 s， i 不等于 s 接了，那接又要向前回退，接怎么回退？找到他的前一位啊？所对应的奈斯的值就是我们要回退的下标前一位。 前一位的 nice 数组的值是一吗？那我们就要回到下标为一的位置，那这里本来就是一，那说明先先回推到这里 接，回退到这里继续比较，别忘了我们这里是 well， 回退是一个持续的过程，继续比较，比较的时候呢，那 si 和 s 接依然不相等，依然不相等的话，接还要向前回退， 那依然还是要看到前一位，前一位零啊。回到下标为零的位置，那接又回到了起始位置， 此时呢，再去比较，那依然不相等，依然不相等，那接已经回到了起始位置，那这样呢，我们在更新 nice 数组的指的时候就是 nice 啊， i 等于接，是吧，那此时就是零， 那这样我们就用我啊，就用这个函数啊，完成了对这个 nice 数组的求职， 大家可以看一下，这个奈斯数组呢，就是一个完整的我们的前缀表啊，没有做任何的移动，那么我们在后面拿这个前缀表去匹配的时候，也可以直接原封不动的啊，就用这个奈斯数组啊来做这 模式串去匹配这个文本串，这样我们就把球奈斯数组的这个过程以及详细的代码都讲出来了。 嗯，大家呢可以有什么疑问呢？可以在我这个视频啊讲解的过程中啊，及时的发弹幕，这样呢，我也可以知道啊大家疑惑的问题。 好了，那我们就讲到这里了，感谢大家的观看。