8月7日周五总结leetcode28匹配字符串代码还没写 还在研究思路我的方法幼稚的模式串匹配思路1、母串和子串同时设置指针同向而行2、母串指针进行遍历有效匹配的极限是母串长减子串长再往后母串不够长了3、当移动到子串第一个字符匹配的字符母串指针和子串指针同时移动3.1、如果全部匹配上侧输出第一个匹配字符的下标3.2、如果中途出现任何不匹配母串指针回到第一个匹配子符的下一位子指针回到下标0然后继续遍历母指针遍历到极限值子指针依然无法遍历到子串结尾则证明完全不匹配标准做法KMP算法做法根据子串构造一个next匹配表遍历主串在下标 i 匹配失败时查询next(i)就是子串接着与母串匹配的位置核心思路值得注意的点KMP的核心当发生不匹配时根据已经匹配成功的部分直接把子串滑动到下一个可能匹配的位置母指针坚决不回退再专业点就是“利用子串内部的重复信息把母串上已经匹配过的信息搬运到子串开头从而跳过那些注定会成功的比较步骤”NEXT----最大相等前后缀数组记录了“子串在发生不匹配时应该跳到哪个位置继续匹配”NEXTj含义子串从0到 j 这一段不包含 j最长相等前后缀的长度做法当你在下标 j 发生不匹配了子指针就回到下标 j 而不是下标0然后继续匹配如何手搓NEXT数组关键什么是“前缀”和“后缀”前缀必须包含第一个字符绝对不能包含最后一个字符这些前缀构成前缀家族后缀必须包含最后一个字符绝对不能包含第一个字符这些后缀构成后缀家族“最长相等前后缀”本质就是子串内部自带的记忆。是子串已匹配的部分中开头和结尾完全相同的最长片段。当发生不匹配时子串可以直接跳过中间那些注定不可能匹配的区域把开头这段直接平移到结尾的位置然后从下一个字符继续匹配什么叫“子串根据Next数组跳跃”注意是跳跃而不是回退利用子串内部已经匹配过的重叠部分把子串直接滑动到下一个可能匹配的位置MySQL进阶篇触发器锁 上面语法是齐次主要是各种概念MySQL整体回顾后面的事务原理貌似上课没讲 周末自己看一下下周工作日考试
8月7日周五总结leetcode28匹配字符串代码还没写 还在研究思路我的方法幼稚的模式串匹配思路1、母串和子串同时设置指针同向而行2、母串指针进行遍历有效匹配的极限是母串长减子串长再往后母串不够长了3、当移动到子串第一个字符匹配的字符母串指针和子串指针同时移动3.1、如果全部匹配上侧输出第一个匹配字符的下标3.2、如果中途出现任何不匹配母串指针回到第一个匹配子符的下一位子指针回到下标0然后继续遍历母指针遍历到极限值子指针依然无法遍历到子串结尾则证明完全不匹配标准做法KMP算法做法根据子串构造一个next匹配表遍历主串在下标 i 匹配失败时查询next(i)就是子串接着与母串匹配的位置核心思路值得注意的点KMP的核心当发生不匹配时根据已经匹配成功的部分直接把子串滑动到下一个可能匹配的位置母指针坚决不回退再专业点就是“利用子串内部的重复信息把母串上已经匹配过的信息搬运到子串开头从而跳过那些注定会成功的比较步骤”NEXT----最大相等前后缀数组记录了“子串在发生不匹配时应该跳到哪个位置继续匹配”NEXTj含义子串从0到 j 这一段不包含 j最长相等前后缀的长度做法当你在下标 j 发生不匹配了子指针就回到下标 j 而不是下标0然后继续匹配如何手搓NEXT数组关键什么是“前缀”和“后缀”前缀必须包含第一个字符绝对不能包含最后一个字符这些前缀构成前缀家族后缀必须包含最后一个字符绝对不能包含第一个字符这些后缀构成后缀家族“最长相等前后缀”本质就是子串内部自带的记忆。是子串已匹配的部分中开头和结尾完全相同的最长片段。当发生不匹配时子串可以直接跳过中间那些注定不可能匹配的区域把开头这段直接平移到结尾的位置然后从下一个字符继续匹配什么叫“子串根据Next数组跳跃”注意是跳跃而不是回退利用子串内部已经匹配过的重叠部分把子串直接滑动到下一个可能匹配的位置MySQL进阶篇触发器锁 上面语法是齐次主要是各种概念MySQL整体回顾后面的事务原理貌似上课没讲 周末自己看一下下周工作日考试
