KMP算法（字符串匹配） KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法。它的核心思想是：当主串与模式串在某一位匹配失败时，模式串能够利用之前已经匹配成功的信息，滑动到某个特定位置继续匹配，而不是像暴力匹配那样只向后移动一位重新开始。这避免了主串指针的回溯，从而将时间复杂度优化到O(n+m)。 1. 问题引入：为什么需要KMP？ 想象一下，你有一个很长的文本（主串，长度为n），和一个相对较短的单词（模式串，长度为m）。你的任务是在文本中找到这个单词第一次出现的位置。 最直观的方法是暴力匹配： 将模式串的起始位置与主串的每一个可能的起始位置对齐。 从对齐的位置开始，逐个字符比较模式串和主串。 如果发现不匹配，就将模式串向后移动一位，然后从头开始比较。 暴力匹配的缺陷 ：当发生不匹配时，主串的指针（索引）会回溯到本次匹配起始位置的下一位。例如，主串"AAAAAAB"，模式串"AAAB"。当匹配到最后一个字符（'A' != 'B'）失败时，暴力匹配会让主串指针回溯，造成大量不必要的重复比较。其时间复杂度在最坏情况下是O(n* m)。 KMP算法就是为了解决这个“指针回溯”问题而诞生的。 2. KMP的核心思想：利用已知信息 KMP算法的精妙之处在于，它预计算了模式串本身的一个特殊数组—— 前缀表 （通常称为 next 数组）。这个数组记录了模式串中“相同前缀后缀的最大长度”信息。 前缀 ：指除了最后一个字符以外，一个字符串的全部头部组合。 后缀 ：指除了第一个字符以外，一个字符串的全部尾部组合。 最长公共（相等）前后缀 ：一个字符串中，最长的、相等的前缀和后缀的长度。 举例理解“最长公共前后缀” ： 模式串"ABABC"： 前缀有："A", "AB", "ABA", "ABAB" 后缀有："C", "BC", "ABC", "BABC" 所有前后缀都不相等，所以最长公共前后缀长度为0。 模式串"ABABA"： 前缀："A", "AB", "ABA", "ABAB" 后缀："A", "BA", "ABA", "BABA" 公共前后缀有："A"（长度为1）和"ABA"（长度为3）。最长的是"ABA"，所以长度为3。 next 数组的作用 ： next[j] 表示模式串中从下标0到j（包含j）的这个子串中，其“最长公共前后缀”的长度。当主串和模式串在第j位匹配失败时， next[j] 的值就告诉我们，应该将模式串滑动到哪个位置，让模式串的 next[j] 位来对准当前主串的指针位置，继续进行比较。 3. 构建next数组（预处理阶段） 构建 next 数组的过程本身就是一个“模式串自我匹配”的过程。我们使用两个指针： i （后缀的末尾）和 j （前缀的末尾，也代表当前最长公共前后缀的长度）。 算法步骤： 初始化： next[0] = 0 （因为单个字符没有真前缀/后缀，长度为0）。令 j = 0 , i = 1 。 开始循环， i 从1遍历到模式串末尾。 情况一 ： pattern[i] == pattern[j] 。这意味着我们找到了更长的公共前后缀。执行 j++ ，然后设置 next[i] = j ，最后 i++ 。 情况二 ： pattern[i] != pattern[j] 。这意味着字符不匹配。 如果 j > 0 ，说明前面有公共部分。我们需要回退 j 。让 j = next[j - 1] 。然后重新比较 pattern[i] 和 pattern[j] 。（这一步是KMP最核心的回退逻辑，可以理解为在模式串内部进行匹配）。 如果 j == 0 ，说明已经退到开头，确实没有公共部分了。设置 next[i] = 0 ，然后 i++ 。 以模式串"aabaaf"为例，构建next数组 ： p = ['a','a','b','a','a','f'] next[0] = 0 (初始化) i=1, j=0 : p[1]('a') == p[0]('a') -> j=1 , next[1]=1 , i=2 i=2, j=1 : p[2]('b') != p[1]('a') -> j>0 , 回退 j = next[0] = 0 i=2, j=0 : p[2]('b') != p[0]('a') -> j==0 , next[2]=0 , i=3 i=3, j=0 : p[3]('a') == p[0]('a') -> j=1 , next[3]=1 , i=4 i=4, j=1 : p[4]('a') == p[1]('a') -> j=2 , next[4]=2 , i=5 i=5, j=2 : p[5]('f') != p[2]('b') -> j>0 , 回退 j = next[1] = 1 i=5, j=1 : p[5]('f') != p[1]('a') -> j>0 , 回退 j = next[0] = 0 i=5, j=0 : p[5]('f') != p[0]('a') -> j==0 , next[5]=0 , 结束。 最终 next 数组为： [0, 1, 0, 1, 2, 0] 4. 使用next数组进行匹配 匹配过程与构建 next 数组的过程非常相似。我们使用两个指针： i 遍历主串， j 遍历模式串。 算法步骤： 初始化： i = 0 （主串指针）， j = 0 （模式串指针）。 循环， i 从0遍历到主串末尾。 情况一 ： text[i] == pattern[j] 。匹配成功， i++ , j++ 。 情况二 ： text[i] != pattern[j] 。匹配失败。 如果 j > 0 ，说明已经匹配了一部分。根据 next 数组回退模式串指针： j = next[j - 1] 。（ 注意：主串指针 i 不回溯！ ） 如果 j == 0 ，说明模式串已经退到开头，无法再退。那么主串指针 i 前进一步： i++ 。 判断结果：如果 j 等于模式串长度 m ，说明匹配成功，返回位置 i - j 。否则，匹配失败。 以主串"aabaabaaf"，模式串"aabaaf"（next=[ 0,1,0,1,2,0]）为例 ： i=0, j=0 : 'a'=='a' -> i=1, j=1 i=1, j=1 : 'a'=='a' -> i=2, j=2 i=2, j=2 : 'b'=='b' -> i=3, j=3 i=3, j=3 : 'a'=='a' -> i=4, j=4 i=4, j=4 : 'a'=='a' -> i=5, j=5 i=5, j=5 : 'b' != 'f' -> j>0 , 回退 j = next[4] = 2 i=5, j=2 : 'b'=='b' -> i=6, j=3 i=6, j=3 : 'a'=='a' -> i=7, j=4 i=7, j=4 : 'a'=='a' -> i=8, j=5 i=8, j=5 : 'f'=='f' -> i=9, j=6 j(6) == pattern.length(6) ，匹配成功！起始位置为 i - j = 9 - 6 = 3 。 总结 ：KMP算法通过预处理模式串得到 next 数组，在匹配失败时利用该数组信息智能地滑动模式串，避免了主串指针的回溯，将字符串匹配的效率提升到了线性级别O(n+m)。理解 next 数组的含义和构建过程是掌握KMP算法的关键。