8月7日（周五）总结

leetcode28：匹配字符串（代码还没写 还在研究思路）

我的方法：幼稚的模式串匹配
思路：
1、母串和子串同时设置指针同向而行；
2、母串指针进行遍历（有效匹配的极限是母串长减子串长，再往后母串不够长了）；
3、当移动到子串第一个字符匹配的字符，母串指针和子串指针同时移动：
3.1、如果全部匹配上侧输出第一个匹配字符的下标；
3.2、如果中途出现任何不匹配，母串指针回到第一个匹配子符的下一位，子指针回到下标0，然后继续遍历；母指针遍历到极限值，子指针依然无法遍历到子串结尾，则证明完全不匹配

标准做法：KMP算法
做法：
根据子串构造一个next匹配表
遍历主串，在下标 i 匹配失败时查询next(i)就是子串接着与母串匹配的位置

核心思路（值得注意的点）：

KMP的核心：

当发生不匹配时，根据已经匹配成功的部分，直接把子串滑动到下一个可能匹配的位置，母指针坚决不回退；再专业点就是“利用子串内部的重复信息，把母串上已经匹配过的信息搬运到子串开头，从而跳过那些注定会成功的比较步骤”

NEXT----最大相等前后缀数组：

记录了“子串在发生不匹配时应该跳到哪个位置继续匹配”
NEXT（j）：
含义：子串从0到 j 这一段（不包含 j）最长相等前后缀的长度
做法：当你在下标 j 发生不匹配了子指针就回到下标 j 而不是下标0然后继续匹配
如何手搓NEXT数组（关键）
什么是“前缀”和“后缀”：
前缀：必须包含第一个字符，绝对不能包含最后一个字符（这些前缀构成前缀家族）
后缀：必须包含最后一个字符，绝对不能包含第一个字符（这些后缀构成后缀家族）
“最长相等前后缀”：
本质就是子串内部自带的记忆。是子串已匹配的部分中，开头和结尾完全相同的最长片段。当发生不匹配时，子串可以直接跳过中间那些注定不可能匹配的区域，把开头这段直接平移到结尾的位置，然后从下一个字符继续匹配

什么叫“子串根据Next数组跳跃”（注意是跳跃而不是回退）：

利用子串内部已经匹配过的重叠部分，把子串直接滑动到下一个可能匹配的位置

---

MySQL：进阶篇

触发器
锁 （上面语法是齐次，主要是各种概念）
MySQL整体回顾
后面的事务原理貌似上课没讲 周末自己看一下
（下周工作日考试）