KMP字符串匹配算法 题目描述 KMP算法用于解决字符串匹配问题：给定一个文本串S和一个模式串P，判断P是否在S中出现，并返回出现的位置。KMP算法的核心在于当匹配失败时，利用已匹配的信息避免从头重新比较，将时间复杂度优化到O(n+m)。 解题过程 1. 暴力匹配的缺陷 暴力匹配的做法是逐个字符比较： 当S[ i]与P[ j ]匹配时，i和j同时后移。 当不匹配时，i回退到本次匹配起始位置的下一个字符，j回退到0。 这种回退导致重复比较，最坏时间复杂度为O(n* m)。 2. KMP的核心思想 KMP算法在匹配失败时，保持文本指针i不回溯，仅移动模式串指针j到一个特定位置。这个位置由"最长公共前后缀"决定。 前缀 ：除最后一个字符外的所有连续子串（必须从首字符开始）。 后缀 ：除第一个字符外的所有连续子串（必须到末字符结束）。 最长公共前后缀 ：前缀和后缀中最长的相同部分。 例如：P="ababc"的前缀有"a","ab","aba","abab"，后缀有"c","bc","abc","babc"，最长公共前后缀为"ab"（长度2）。 3. 构建next数组 next数组（或称部分匹配表）存储模式串每个位置之前子串的最长公共前后缀长度。定义next[ j]为当P[ j ]匹配失败时，j应该跳转的位置。 计算next数组的步骤（以P="ababc"为例）： j=0：子串"a"无前后缀，next[ 0 ]=-1（特殊标记，表示整体右移）。 j=1：子串"ab"：前缀[ "a"]，后缀[ "b"]，无公共部分，next[ 1 ]=0。 j=2：子串"aba"：前缀[ "a","ab"]，后缀[ "a","ba"]，公共部分"a"长度1，next[ 2 ]=1。 j=3：子串"abab"：前缀[ "a","ab","aba"]，后缀[ "b","ab","bab"]，公共部分"ab"长度2，next[ 3 ]=2。 j=4：子串"ababc"：前缀[ "a","ab","aba","abab"]，后缀[ "c","bc","abc","babc"]，无公共部分，next[ 4 ]=0。 最终next=[ -1,0,1,2,0 ]。 4. 匹配过程 假设S="abababc"，P="ababc"，next=[ -1,0,1,2,0 ]： i=0,j=0：S[ 0]='a'匹配P[ 0 ]='a'，i=1,j=1。 i=1,j=1：S[ 1]='b'匹配P[ 1 ]='b'，i=2,j=2。 i=2,j=2：S[ 2]='a'匹配P[ 2 ]='a'，i=3,j=3。 i=3,j=3：S[ 3]='b'匹配P[ 3 ]='b'，i=4,j=4。 i=4,j=4：S[ 4]='a'不匹配P[ 4]='c'，查next[ 4 ]=0，j跳转到0。 i=4,j=0：S[ 4]='a'匹配P[ 0 ]='a'，i=5,j=1。 继续匹配直至j=5（越界），匹配成功，起始位置为i-j=5-5=0。 5. 关键点总结 next数组的构建和匹配过程均通过双指针模拟，避免回溯。 理解最长公共前后缀是掌握KMP的关键。 实际编码时需注意next数组的边界处理（如j=-1时整体移动）。