KMP算法 |
您所在的位置：网站首页 › kmp算法next数组计算方法 › KMP算法 |
KMP算法
|
1.kmp算法基本介绍
KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。
2.字符串的最长公共前后缀&部分匹配表
2.1 什么是最长公共前后缀
1️⃣ 字符串的前缀是指不包含最后一个字符的所有以第一个字符（索引为0）开头的连续子串 比如字符串 “ABABA” 的前缀有：A，AB，ABA，ABAB 2️⃣ 字符串的后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串 比如字符串 “ABABA” 的后缀有：BABA，ABA，BA，A 3️⃣ 公共前后缀：一个字符串的 所有前缀连续子串 和 所有后缀连续子串 中相等的子串 比如字符串 “ABABA” 前缀有：A，AB，ABA，ABAB后缀有：BABA，ABA，BA，A因此公共前后缀有：A ，ABA 4️⃣ 最长公共前后缀：所有公共前后缀 的 长度最长的 那个子串 比如字符串 “ABABA” ，公共前后缀有：A ，ABA 由于 ABA 是 三个字符长度，A 是一个字符长度，那么最长公共前后缀就是 ABA 📝 再比如说一个字符串 str = “ABCABD” 对于str从 索引为0 开始的子串 “A” 而言： 前缀：不包含最后一个字符A的 所有以第一个字符A开头 的 连续子串 不存在后缀：不包含第一个字符A 的 所有以最后一个字符A结尾 的 连续子串 不存在因此该子串的最长公共前后缀 为 0 对于str从 索引为0 开始的子串 “AB” 而言： 前缀：不包含 最后一个字符B 的 所有以第一个字符A开头 的 连续子串 有 —— “A”后缀：不包含 第一个字符A 的 所有以最后一个字符B结尾 的 连续子串 有 —— “B”因此该子串的最长公共前后缀 为 0 对于str从 索引为0 开始的子串 “ABC” 而言： 前缀：不包含 最后一个字符C 的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”后缀：不包含 第一个字符A 的 所有以最后一个字符C 结尾 的 连续子串有 —— “BC”，“C”前缀与后缀的连续子串不存在相同的，因此该子串的最长公共前后缀 为 0 对于str从 索引为0 开始的子串 “ABCA” 而言： 前缀：不包含 最后一个字符A 的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”，“ABC”后缀：不包含 第一个字符A 的 所有以最后一个字符A 结尾 的 连续子串有 —— “BCA”，“CA”，“A”前缀与后缀的连续子串中存在相同且最长的子串 A，因此该子串的最长公共前后缀 为 1 对于str从 索引为0 开始的子串 “ABCAB” 而言： 前缀：不包含 最后一个字符B 的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”，“ABC”，“ABCA”后缀：不包含 第一个字符A 的 所有以最后一个字符B 结尾 的 连续子串有 —— “BCAB”，“CAB”，“AB”，“B”前缀与后缀的连续子串中存在相同且最长的子串 AB，因此该子串的最长公共前后缀 为 2 对于str从 索引为0 开始的子串 “ABCABD” 而言： 前缀：不包含 最后一个字符D 的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”，“ABC”，“ABCA”，“ABCAB”后缀：不包含 第一个字符A 的 所有以最后一个字符D 结尾 的 连续子串有 —— “BCABD”，“CABD”，“ABD”，“BD”，“D”前缀与后缀的连续子串不存在相同的，因此该子串的最长公共前后缀 为 0 2.2 什么是部分匹配表Next个人理解：对于字符串str，从 第一个字符开始的每个子串 的 最后一个字符 与 该子串的最长公共前后缀的长度 的对应关系表格。这个表我们以 int[] next 数组方式进行存储。 比如说上面举的例子： 子串 “A”：最后一个字符是 A，该子串的最长公共前后缀长度是 0，因此对应关系就是 A - 0子串 “AB”：最后一个字符是 B，该子串的最长公共前后缀长度是 0，因此对应关系就是 B - 0子串 “ABC”：最后一个字符是 C，该子串的最长公共前后缀长度是 0，因此对应关系就是 C - 0子串 “ABCA”：最后一个字符是 A，该子串的最长公共前后缀长度是 1，因此对应关系就是 A - 1子串 “ABCAB”：最后一个字符是 B，该子串的最长公共前后缀长度是 2，因此对应关系就是 B - 2子串 “ABCABD”：最后一个字符是 D，该子串的最长公共前后缀长度是 0，因此对应关系就是 D - 0因此综上，我们说该字符串 str 的部分匹配表为： ABCABD000120那么对应的next数组就是 int[] next = {0, 0, 0, 1, 2, 0} 2.3 字符串最长公共前后缀&部分匹配表的代码实现
下面的代码可以参考图中实例进行分析： /** * 获取一个字符串 pattern 的部分匹配表 * * @param patternStr 用于模式匹配字符串 * @return 存储部分匹配表的每个子串的最长公共前后缀的 next数组 */ public static int[] kmpNext(String patternStr) { //将 patternStr 转为 字符数组形式 char[] patternArr = patternStr.toCharArray(); //预先创建一个next数组，用于存储部分匹配表的每个子串的最长公共前后缀 int[] next = new int[patternStr.length()]; /* 从第一个字符（对应索引为0）开始的子串，如果子串的长度为1，那么肯定最长公共前后缀为0 因为这唯一的一个字符既是第一个字符，又是最后一个字符，所以前后缀都不存在 -> 最长公共前后缀为0 */ next[0] = 0; /* len有两个作用： 1. 用于记录当前子串的最长公共前后缀长度 2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1]/当前子串最长公共前缀字符串的下一个字符的索引 最长公共前后缀为0 */ next[0] = 0; /* len有两个作用： 1. 用于记录当前子串的最长公共前后缀长度 2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1]/当前子串最长公共前缀字符串的下一个字符的索引 |
【本文地址】
今日新闻 |
推荐新闻 |