KMP算法的进一步优化

本节内容KMP算法进⼀步优化研/CSKAOYANKMP算法根据模式串T，求

利⽤next数组进⾏匹配出next数组

（主串指针不回溯）T=‘abaabc’next数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]011223if(S[i]!=T[j])j=next[j];if(j==0){i++;j++}KMP算法，最坏时间复杂度O(m+n)其中，求next数组时间复杂度O(m)模式匹配过程最坏时间复杂度O(n)研/CSKAOYAN⼿算求next数组的⽅法根据模式串T，求出next数组T=‘abaabc’next数组:next[1]都⽆脑写0

next[2]都⽆脑写1next[0]next[1]next[2]next[3]next[4]next[5]next[6]011223其他next：在不匹配的位置前，划⼀根美丽的分界线

if(S[i]!=T[j])j=next[j];模式串⼀步⼀步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为⽌。此时j指向哪⼉，next数组值就是多少if(j==0){i++;j++}KMP算法，最坏时间复杂度O(m+n)其中，求next数组时间复杂度O(m)模式匹配过程最坏时间复杂度O(n)研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]011223研/CSKAOYANnext数组的优化思路i主串S：123456789101112131415???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]011223研/CSKAOYANnext数组的优化思路i主串S：123456789101112131415ab?????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]011223研/CSKAOYANnext数组的优化思路⼀定不是ai主串S：123456789101112131415ab?????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]011223研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i主串S：123456789101112131415???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i主串S：123456789101112131415ab?????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路⼀定不是ai主串S：123456789101112131415ab?????????????模式串T：abaabcj123456next数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i主串S：123456789101112131415ab?????????????模式串T：abaabc123456jnext数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：abaa???????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路⼀定不是bi123456789101112131415主串S：abaa???????????模式串T：abaabc123456jnext数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路⼀定不是bi123456789101112131415主串S：abaa???????????模式串T：abaabc123456jnext数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]010223研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路⼀定不是bi123456789101112131415主串S：abaa???????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路⼀定不是bi123456789101112131415主串S：abaa???????????模式串T：abaabc123456jnext数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路i123456789101112131415主串S：???????????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路⼀定不是ci123456789101112131415主串S：abaab??????????模式串T：abaabc123456next数组:jnext[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANnext数组的优化思路但有可能是ai123456789101112131415主串S：abaab??????????模式串T：abaabc123456jnext数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]010213研/CSKAOYANKMP算法的进⼀步优化根据模式串T，求

利⽤next数组进⾏匹配出next数组（主串指针不回溯）使⽤nextval数组T=‘abaabc’next数组:next[0]next[1]next[2]next[3]next[4]next[5]next[6]011223优化nextval数组:nextval[0]nextval[1]nextval[2]nextval[3]nextval[4]nextval[5]nextval[6]010213研/CSKAOYAN练习1：求nextval数组模式串T=ababaaababaa序号j123456模式串ababaanext[j]011234⼿算解题：先求next数组，再由next数组求nextval数组

研/CSKAOYAN练习1：求nextval数组模式串T=ababaaababaa序号j123456模式串ababaanext[j]011234⼿算解题：先求next数组，再由next数组求nextval数组

序号j123456模式串ababaanextval[j]010104研/CSKAOYAN练习2：求nextval数组模式串T=aaaabaaaab序号j12345模式串aaaabnext[j]01234⼿算解题：先求next数组，再由next数组求nextval数组

研/CSKAOYAN练习2：求nextval数组模式串T=aaaabaaaab序号j12345模式串aaaabnext[j]01234⼿算解题：先求next数组，再由next数组求nextval数组

序号j12345模式串aaaabnextval[j]00004研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaabj12345序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化前）i123456789101112131415主串S：aaacaaaabdaaaab模式串T：aaaab12345j序号j12345模式串aaaabnext[j]01234研/CSKAOYAN例：KMP算法（优化后）i123456789101112131415主串S：aaacaaaabdaaaab