数据结构串的模式匹配朴素匹配KMPnextval说明本文下标从 1 开始文章目录数据结构串的模式匹配朴素匹配KMPnextval说明本文下标从 1 开始1.基本概念子串与模式串的区别2.朴素模式匹配算法核心思想字符匹配失败时匹配成功3.KMP算法核心思想时间复杂度4.next数组的计算next[j]的含义规则例1T ababaa例2T aaaab5.KMP算法的进一步优化nextval数组的计算例1T ababaa例2T aaaab1.基本概念模式匹配是指在主串中查找与模式串待搜索的字符串完全相同的子串并返回其首次出现的位置子串与模式串的区别子串是主串的一部分在主串中一定存在模式串待搜索的字符串在主串中不一定存在2.朴素模式匹配算法朴素模式匹配算法的时间复杂度O(mn)核心思想逐个对比主串和模式串的字符如果字符匹配不成功模式串回溯到第一个位置主串回溯到本轮起始位置的下一个位置重新匹配直到找到主串中与模式串完全相同的子串返回子串起始位置字符匹配失败时i i - (j - 1) 1 i - j 2j 1匹配成功返回模式串在主串中首次出现的位置return i - T.length;3.KMP算法KMP算法是对朴素模式匹配算法的优化核心思想匹配失败时i不回退仅通过预处理得到的next数组调整 j 的位置避免了重复字符的比较从而将时间复杂度从O(mn)优化为O(m n)时间复杂度预处理next数组 O(m)匹配 O(n)总时间复杂度 O(m n)4.next数组的计算next[j]的含义当模式串的第j个字符失配时下一轮应从模式串的next[j]位置开始比较规则next[1] 0next[2] 1从模式串的第三个字符开始next数组的值是模式串中当前字符之前的串的最长公共前后缀的长度1例1T ababaa下标123456next011234next[1] 0, next[2] 1从模式串的第3个字符 a 开始第3个字符 a 前面是 “ab”没有公共前后缀所以next[3] 0 1 1第4个字符 b 前面是 “aba”最长公共前后缀是 “a”长度是1所以next[4] 1 1 2第5个字符 a 前面是 ”abab”最长公共前后缀是 “ab”长度是2所以next[5] 2 1 3第6个字符 a 前面是 “ababa”最长公共前后缀是 “aba”长度是3所以next[6] 3 1 4例2T aaaab下标12345next01234next[1] 0, next[2] 1从模式串的第3个字符 a 开始第3个字符 a 前面是 “aa”最长公共前后缀是”a”所以next[3] 1 1 2第4个字符 a 前面是 “aaa”最长公共前后缀是 “aa”长度是2所以next[4] 2 1 3第5个字符 b 前面是 ”aaaa”最长公共前后缀是 “aaa”长度是3所以next[5] 3 1 4[注意] 字符串的公共前后缀不包含字符串本身如字符串”aaa”的公共前后缀是”aa”而不是”aaa”5.KMP算法的进一步优化在使用KMP算法进行模式匹配时如果模式串j对应的字符和主串i对应字符不相等失配则将j移动至next[j]继续匹配但j移动后指向的字符可能和移动前指向的字符相同此时出现了重复的比较并且一定会失配所以可以使用nextval数组优化这种重复比较的情况nextval数组的计算nextval[1] 0从第 2 个字符开始当模式串中j对应的字符和next[j]对应的字符相等时nextval[j]的值等于next[j]的nextval值即nextval[j] nextval[next[j]]当模式串中 j 对应的字符和next[j]对应的字符不相等时nextval[j]的值等于next[j]的值即nextval[j] next[j]例1T ababaa下标123456next011234nextval010104nextval[1] 0从模式串的第2个字符 a 开始next[2] 1T.ch[1] aT.ch[2] b字符不相等 - nextval[2] next[2] 1next[3] 1T.ch[1] aT.ch[3] a字符相等 - nextval[3] nextval[next[3]] 0next[4] 2T.ch[2] bT.ch[4] b字符相等 - nextval[4] nextval[next[4]] 1next[5] 3T.ch[3] aT.ch[5] a字符相等 - nextval[5] nextval[next[5]] 0next[6] 4T.ch[4] bT.ch[6] a字符不相等 - nextval[6] next[6] 4例2T aaaab下标12345next01234nextval00004nextval[1] 0从模式串的第2个字符 a 开始next[2] 1T.ch[1] aT.ch[2] a字符相等 - nextval[2] nextval[next[2]] 0next[3] 1T.ch[1] aT.ch[3] a字符相等 - nextval[3] nextval[next[3]] 0next[4] 2T.ch[2] aT.ch[4] a字符相等 - nextval[4] nextval[next[4]] 0next[5] 3T.ch[3] aT.ch[5] b字符不相等 - nextval[5] next[5] 4
