20210421

回顾 | GS2-C1-660-16~25 | 数据结构-串（二）| 田静语法C4-S3

Table of Contents

今天二刷660题目第一章16~25题。

全在笔记上啦。

简单地说就是，对主串中的每一个字符作为字串开头，与要匹配的字符串进行匹配，对主串做大循环，每个字符开头做模式串长度大小的小循环，直到匹配成功全部遍历完成为止。

效率低的原因：比较指针会往回跑即比较指针回溯。

KMP算法是指快速地从一个子串中找出你想要的子串（模式串）。(不快不叫KMP噢！)

过程：如上图检查到箭头位置不匹配的时候，箭头所指左边那部分有两个子串是完全匹配的，称之为模式串的公共前后缀，然后往前移动模式串，使得其公共前后缀的前缀直接移动到后缀所在位置。

❗ 找公共前后缀的约束条件：找最长的且长度小于比较指针左端子串长度的。下面看找公共前后缀的例子：

但是字符串一般存在于字符数组中，数组在内存中不可能是移动的，所以上面演示只是形象化的过程，要转化为计算机方便处理的方式。其实只需要研究模式串即可,如下图，扔掉主串只研究模式串即可。

九种状语从句，五种常考。时间、原因、结果、条件、让步状语从句。

有一个单词值得注意：

as：

引导什么状语从句，依靠代入法，看哪个意思代入句子中合适。