字符串匹配是数据结构中一个看似简单、实则暗藏玄机的问题。绝大多数考生第一次接触它时，脑子里蹦出来的都是那个朴素的暴力算法：拿模式串在主串上从头到尾一个一个比，失配了就往后挪一格重来。这个方法当然正确，但它的效率在特定场景下会变得十分难看。软考软件设计师考试每年都会在字符串这一章上出题，而其中最让考生头疼、又最容易被命题人拿来做区分度的，就是KMP算法及其核心产物next数组。本文不从"背公式"的角度切入，而是把KMP背后的失配回溯思想一层层拆开，让读者真正理解为什么主串指针可以永不回退、为什么next数组的递推构造是正确的，进而在考场上无论命题人怎么换花样都能从容应对。
在进入KMP之前，必须先厘清几个最基本的概念，否则后续的推导会失去根基。串是由零个或多个字符组成的有限序列，在软考语境下通常记为S，其字符个数称为串的长度。一个长度为n的主串S，与一个长度为m的模式串T（也常写作P，即Pattern），模式匹配问题的目标是在S中寻找所有等于T的子串的起始位置，若不存在则返回一个表示失败的标记。这里有两个关键约束需要特别留意：其一，模式匹配要求的是"完全相等"，不是"包含公共部分"；其二，匹配通常从左向右进行，主串和模式串的字符按位置逐一比较。此外需要明确的是，这里的主串和模式串都是广义的符号序列，既可以是字符，也可以是任何可以比较相等性的元素序列，软考语境下默认为字符序列。
要准确理解模式匹配，还必须掌握串这一抽象数据类型的基本术语。串的字符位置从0或从1开始编号，这个起点约定会直接影响到next数组的数值，是软考命题反复做文章的地方。子串是由串中任意连续字符组成的子序列，包含空串；主串是包含子串的那个串；任意串都是它自身的子串，但"真子串"则要求必须严格短于原串。串在计算机中的存储通常有定长顺序存储、堆分配存储和块链存储三种方式，软考偶尔会在选择题中考查定长顺序存储"截断"的现象，即当串长超过预分配的数组长度时，多余字符被丢弃。此外，串的两种基本运算——串比较与求子串——在顺序存储下都能以线性时间完成，而串的拼接和子串提取则是许多字符串算法的基础原语。理解串的连续性和有序性，是理解"前后缀"这一KMP核心概念的前提，因为前缀和后缀正是建立在"从串首开始"和"以串尾结束"这两个严格的位置约定之上的。
在正式展开KMP之前，先把模式匹配这一类问题的算法家族梳理清楚，有助于建立全局认知。模式匹配算法按照一次能匹配的模式串数量，可以分为单模式匹配和多模式匹配两大类。单模式匹配算法中，最基础的是朴素匹配法，复杂度为O(n×m)；在此基础上发展出了KMP算法、Boyer-Moore算法和Rabin-Karp算法，它们分别用不同的手段把最坏或平均复杂度降下来。KMP通过失配回溯保证最坏情况线性；Boyer-Moore利用坏字符规则和好后缀规则从右向左比较，在实际文本中往往更快；Rabin-Karp则借助哈希值快速排除不可能的位置。多模式匹配的代表是AC自动机，它把KMP的失配思想推广到字典树上，实现一次扫描同时匹配多个模式。软考软件设计师考试的重点是KMP，因为它的next数组既适合出客观题，又能检验考生对字符串性质的理解深度，同时它也是理解其他高级匹配算法的基础。建立起这张图景后，再回到KMP的具体细节，就不会陷入只见树木不见森林的困境。
朴素匹配算法的思路极其直观：从主串的第一个字符开始，与模式串的第一个字符对齐比较，如果当前位置的字符相等，则两个指针同时后移；一旦失配，模式串整体向右滑动一个位置，主串指针回退到本次匹配起始位置的下一个字符，重新开始比较。这个算法在最坏情况下的时间复杂度是O(n×m)。理解它为什么慢，是理解KMP价值的第一块基石。考虑一个极端例子：主串为连续n个字符a后接一个字符b，模式串为连续m个字符a后接一个字符b。朴素算法在每一次尝试中都要比较m次，直到最后一个字符才发现b与a不匹配，然后主串指针只回退一位，再次比较m次。总比较次数逼近n×m。问题的根源在于，朴素算法在失配时把已经获得的匹配信息全部丢弃了：明明已经知道模式串的前若干个字符与主串的某一段完全相等，却要主串指针退回重来，把这一段重新扫描一遍。KMP算法的全部精髓，就是设法保留这些已经匹配的信息，让主串指针只进不退。
理解KMP，最关键的一步是完成一次思想的飞跃：从"失配后一切重来"到"失配后利用已知信息聪明地滑动"。朴素匹配的思维惯性是，一旦比较失败，就把模式串整体挪一格，从头再来，仿佛之前的比较白做了。而KMP的洞察在于，前面成功匹配的那一段里，蕴含着模式串自身结构的信息，这些信息与主串无关，只取决于模式串本身，因此可以预先计算出来。具体来说，当模式串已经匹配了j个字符时，这j个字符构成的子串是已知的，它的前后缀重叠情况也是已知的，那么在失配时模式串能滑多远、下一次该从模式串的哪个位置继续比较，都可以提前算好存起来，这就是next数组的由来。这个"预处理模式串自身"的思想，是KMP区别于朴素匹配的根本，也是本文后续所有推导的逻辑起点。
KMP的核心概念是前缀、后缀以及它们之间的关系。对于模式串T中的任意前缀子串，可以考察它的"真前缀"和"真后缀"。真前缀是指除自身外、从第一个字符开始的所有子串；真后缀是指除自身外、以最后一个字符结尾的所有子串。所谓最长相等前后缀，就是对于一个给定的子串，找出既是它的真前缀、又是它的真后缀、且长度最长的那个子串的长度。这个值在KMP里被称为部分匹配值，英文缩写PM，用一张表记录下来就是部分匹配表PMT。举例说明：对于子串"abab"，它的真前缀有"a""ab""aba"，真后缀有"bab""ab""b"，其中公共且最长的是"ab"，因此"abab"的部分匹配值为2。这个"2"的含义极其重要：它意味着当模式串匹配到"abab"这一步时，前两个字符与后两个字符是相同的，因此在失配发生时，模式串可以向前滑动，让前缀部分直接顶替后缀部分的位置，而无须重新比较。
为了把"最长相等前后缀"这个概念彻底落到可操作层面，有必要完整推演一个具体模式串的部分匹配表。取模式串T为"abaabcac"，共8个字符，下标从0到7。逐个考察每个前缀子串：前缀"a"长度为1，真前缀和真后缀都为空，部分匹配值为0；前缀"ab"，真前缀只有"a"，真后缀只有"b"，二者不相等，值为0；前缀"aba"，真前缀有"a""ab"，真后缀有"ba""a"，公共且最长的是"a"，值为1；前缀"abaa"，真后缀有"baa""aa""a"，与真前缀"a""ab""aba"的公共最长项是"a"，值为1；前缀"abaab"，末尾字符是b，真后缀"aab""ab""b"，与真前缀"a""ab""aba""abaa"的公共最长项是"ab"，值为2；前缀"abaabc"，末尾字符是c，真后缀"aabc""abc""bc""c"，与真前缀的公共最长项为0；前缀"abaabca"，末尾字符回到a，真后缀中"a"与真前缀"a"相等，值为1；前缀"abaabcac"，末尾字符是c，与首字符a不相等，值为0。于是得到部分匹配值序列为0、0、1、1、2、0、1、0。这个逐字符推导的过程，正是考场上求解next数组的原始依据，也是最不容易出错的方法。
部分匹配表描述了每个前缀子串的自我重叠程度，但在实际匹配过程中，我们更常用的是next数组。next数组是PMT的一种平移变形，它的定义是：next[j]表示当模式串的第j个字符与主串失配时，模式串指针应当回退到的下标。这里的下标约定对解题影响极大，软考题目既可能从0开始编号，也可能从1开始编号，两者对应的next数组数值会整体偏移，这是本文后面要专门展开的误区之一。以从0开始编号为例，next[0]约定为-1，表示连第一个字符都失配时，模式串指针需要移动到-1这个虚拟位置，实际效果是模式串整体向右滑动一格，同时主串指针前进一格。从0开始编号时，next数组恰好等于部分匹配表整体右移一位、首位置-1；从1开始编号时，next[1]约定为0，next数组等于部分匹配表整体右移一位、首位置0。两种约定下，next[j]的数值相差1，但表达的回退语义完全一致。考生务必在动笔前先看清题目的编号起点。
next[j]的递推构造遵循这样一条规律：已知next[0]到next[j-1]，要求next[j]时，先看T[j-1]是否等于T[next[j-1]]；若相等，则next[j]=next[j-1]+1；若不相等，则沿着next链继续回退，令k=next[next[j-1]]，再比较T[j-1]与T[k]，直到找到相等的位置或者回退到-1为止。这条递推规则背后的直观含义是：next数组的构造过程，本质上是模式串与自身进行的一次KMP匹配。以模式串"abaabcac"为例，从0开始编号，next[0]=-1是初始约定；求next[1]时看T[0]='a'与T[next[0]]即T[-1]这个虚拟位置，由于next[0]为-1，直接令next[1]=0；求next[2]时，比较T[1]='b'与T[next[1]]=T[0]='a'，不相等，回退到next[0]=-1，于是next[2]=0；求next[3]时，比较T[2]='a'与T[next[2]]=T[0]='a'，相等，于是next[3]=next[2]+1=1。依此类推可以得到完整的next数组为-1、0、0、1、1、2、0、1。这个递推过程的关键，在于失配时不是简单置0，而是要沿着next链回溯，这一步的遗漏是考生最常犯的错误。
理解了next数组的定义后，最关键的问题是：为什么失配时模式串指针回退到next[j]是正确的，为什么不会漏掉任何可能的匹配？假设模式串T与主串S在某次对齐中，已经成功匹配了前j个字符，即S[i-j]到S[i-1]这一段与T[0]到T[j-1]这一段完全相等。现在T[j]与S[i]失配。朴素算法的做法是让模式串只滑一格，从S[i-j+1]重新开始比较；而KMP断言，模式串可以直接滑到某个更远的位置，让T的某个前缀与已经匹配段的后缀对齐。这个断言成立的前提
本篇完！