括号匹配的原理_判断括号是否匹配的算法

KMP 模式匹配详解通俗易懂　　KMP 模式匹配详解通俗易懂　　KMP 模式匹配是解决字符串匹配的问题　　一、原始的字符串暴力匹配　　要点：子串的第一个字符匹配成功主串的字符后就依次匹配子串后面的字符，直到子串匹配结束　　代码：　　下面是主串 “abcdefgab” 子串 “abcdex” 的原始暴力匹配流程　　

　　暴力匹配存在的问题：　　每次匹配失败都可以得出 2 个结论：当前字符匹配失败（比如步骤 1 的「红色线」）当前匹配字符前面的字符匹配成功（比如步骤 1 的「绿色线」）　　暴力匹配并没有有效利用第二条结论。 KMP 模式匹配算法利用第二条结论，是一个效率极高 O(n+m) 的字符串匹配算法　　二、KMP 模式匹配算法　　2.1 减少主串指针「回溯」　　

　　什么是「回溯」: 　　还是刚刚例子：在第 1 步中，主串的指针一步一步匹配增加到了第 2 步中，因为第一步匹配失败都「回溯」到了　　指针增加然后又减少，这就是「回溯」　　如何减少「回溯」：　　还是刚刚的例子：上图的步骤 1 主串 “abcdefgab” 匹配了子串前面的 5 个字符 “abcde”（看「绿色线」）子串 “abcdex” 的首字母 “a” 和后面的 “bcdex” 都不相等。意味着子串上的首字符 “a” 必然不可能再与主串上的前面 5 个字符 “bcde” 匹配（看绿色线）　　按照我们人类的思维，上图的 2、3、4、5 步都是多余的。（这个人类的思维也是理解 KMP 算法的关键）　　如果我们减少了 2、3、4、5 步骤就「减少了回溯」　　减少主串指针「回溯」：　　上面的例子当我们减少完 2、3、4、5 步骤之后。　　只剩下 1 和 6 步骤：　　

　　我们发现主串指针没有再发生回溯了，只有指针子串指针回溯到了。　　子串指针回溯的位置也是有讲究的（能回溯到 0 的原因是：子串 “abcdex” 的首字母 “a” 和后面的 “bcdex” 都不相等）子串回溯的位置取决于匹配字符前面的字符串的「最长前后缀相同长度」　　2.1 最长前后缀相同长度　　定义：前缀：组成包含第一个字符，不包含最后一个字符后缀：组成包含最后一个字符，不包含第一个字符最长前后缀长度：：前缀后缀相等最长的素　　（前缀后缀补不能为同一个素，比如：在中，前缀后缀不能同时为，这个「最长前后缀长度」为 0）　　举个例子中：前缀有：a、ab、abc、abcd 后缀有：e、de、cde、bcde 最长前后缀相同长度：为 0 　　子串回溯的位置取决于匹配字符前面的字符串的「最长前后缀相同长度」所以子串指针回溯到

　　求「最长前后缀相同长度」习题（建议自己推导一遍）：　　有人就会问，如果T串后面也含有首字符“a”的字符怎么办呢？　　（1）例子 1 aaaaa 前缀有：a、aa、aaa、aaaa 后缀有：a、aa、aaa、aaaa 最长的前后缀相同长度：4 　　子串回溯的位置取决于匹配字符前面的字符串的「最长前后缀相同长度」所以子串指针回溯到

　　（2）例子 2 ababa 前缀有：a、ab、aba、abab 后缀有：a、ba、aba、baba 最长的前后缀相同长度：3 　　子串回溯的位置取决于匹配字符前面的字符串的「最长前后缀相同长度」所以子串指针回溯到

　　2.3 数组　　我们通过「最长前后缀相同长度」求出匹配单个匹配字符的回溯的位置　　数组就是记录子串所以字符的回溯位置子串回溯位置公式如下:，当时候，当时　　（1）例子 1 abcdex 匹配字符前面的字符串为 null，所以（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」（这个点其实也是固定的）匹配字符前面的字符串为 ab ，所以「最长前后缀相同长度」匹配字符前面的字符串为 abc ，所以「最长前后缀相同长度」匹配字符前面的字符串为 abcd ，所以「最长前后缀相同长度」匹配字符前面的字符串为 abcde ，所以「最长前后缀相同长度」　　综上　　（2）例子 2 aaaaax 匹配字符前面的字符串为 null，所以「最长前后缀相同长度」（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」（这个点其实也是固定的）匹配字符前面的字符串为 aa ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aaa ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aaaa ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aaaaa ，所以「最长前后缀相同长度」　　综上　　（3）例子 3 ababax 匹配字符前面的字符串为 null，所以「最长前后缀相同长度」（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」（这个点其实也是固定的）匹配字符前面的字符串为 ab ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aba ，所以「最长前后缀相同长度」匹配字符前面的字符串为 abab ，所以「最长前后缀相同长度」匹配字符前面的字符串为 ababa ，所以「最长前后缀相同长度」　　综上　　2.4 通过 next[] 实现的 KMP 算法代码　　代码　　测试　　输出　　三、算法优化改进　　3.1 问题　　KMP 算法还是存在缺陷比如上面的「例子 2」主串为 “aaaaabgab” 从串为 “aaaaax” 　　（1）求出　　同理「例子 2」 aaaaax 匹配字符前面的字符串为 null，所以「最长前后缀相同长度」（这个点是固定的，有的地方用的是 0 值，都是对的思路都一样）匹配字符前面的字符串为 a ，所以「最长前后缀相同长度」（这个点其实也是固定的）匹配字符前面的字符串为 aa ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aaa ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aaaa ，所以「最长前后缀相同长度」匹配字符前面的字符串为 aaaaa ，所以「最长前后缀相同长度」　　综上　　（2）通过 KMP 部分流程如下　　

　　通过人类的思维我们可以发现：子串 “aaaaax” 的前 4 个字符 a 与第 5 个字符 a 是相等的在 2 步骤中，第 5 个字符 a 匹配失败，意味着前面 4 个 a 必然匹配失败。所以 3、4、5、6 步骤是多余的，因为后面的已经不匹配了，前面的也必然不能匹配　　3.2 算法　　下面参考子串：”aaaaax” 　　问题的关键是：后面的第已经不匹配了，前面的也必然不能匹配　　所以：，固定值，将相同字符的值，等于给他前面的相同的字符，将相同字符的值，等于给他前面的相同的字符，将相同字符的值，等于他前面的相同的字符，将相同字符的值，等于他前面的相同的字符第五个字符和前面的不相等，　　所以我们只需要在前面求 next[] 数组的地方添加一个判断　　对比之前求：　　四、最后　　视频教程

括号匹配的原理_判断括号是否匹配的算法

相关推荐