软考题库
软件设计师 · 高频练习

KMP 匹配到 ABABA 后失配，最长相等前后缀长度是多少？

中级 单选题 第 859 题 中等 软件设计师KMP算法字符串匹配最长相等前后缀前缀函数
内容整理：软考题库编辑部 最近更新：
题目

模式串 P="ABABAC"。KMP 匹配过程中，前 5 个字符 ABABA 已经匹配成功，但在比较第 6 个字符 C 时发生失配。已匹配部分 ABABA 的最长相等真前缀和真后缀长度为（）。

A 0
B 3
C 4
D 5
题目类型：原创高频练习题 用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。
正确答案
B
答案解析

ABABA 的真前缀包括 A、AB、ABA、ABAB，真后缀包括 A、BA、ABA、BABA。两组中最长的相同字符串是 ABA，长度为 3。因此发生失配时，KMP 可以保留末尾已经匹配的 ABA，并把它与模式串开头的 ABA 对齐，而不必把文本指针退回重来。

选项分析

A

错误。首字符 A 同时也是末字符 A，至少存在长度为 1 的相等前后缀，不会回退到完全不保留。

B

正确。最长相等真前缀和真后缀都是 ABA，长度为 3。

C

错误。长度为 4 的真前缀是 ABAB，真后缀是 BABA，两者并不相同。

D

错误。真前缀和真后缀都不能等于字符串本身；长度 5 属于完整字符串，不是真前缀。

本题为什么容易错

最容易丢分的地方有两个：一是漏掉“真”字，把完整字符串也算进去；二是只看到开头和结尾都是 A，就急着填 1，没有继续向更长的 ABA 检查。

先看结论

简短答案

KMP 匹配到 ABABA 后失配，最长相等前后缀长度是多少，正确答案是 B（3）。ABABA 的真前缀包括 A、AB、ABA、ABAB，真后缀包括 A、BA、ABA、BABA。两组中最长的相同字符串是 ABA，长度为 3。因此发生失配时，KMP 可以保留末尾已经匹配的 ABA，并把它与模式串开头的 ABA 对齐，而不必把文本指针退回重来。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
0 本题干扰项 错误。首字符 A 同时也是末字符 A，至少存在长度为 1 的相等前后缀，不会回退到完全不保留。 看到该词不要急着选，先判断是否真正解决题干问题
3 本题正确答案 正确。最长相等真前缀和真后缀都是 ABA，长度为 3。 看到题干核心场景时优先联想到它
4 本题干扰项 错误。长度为 4 的真前缀是 ABAB，真后缀是 BABA，两者并不相同。 看到该词不要急着选，先判断是否真正解决题干问题
5 本题干扰项 错误。真前缀和真后缀都不能等于字符串本身；长度 5 属于完整字符串，不是真前缀。 看到该词不要急着选，先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • 0：错误。首字符 A 同时也是末字符 A，至少存在长度为 1 的相等前后缀，不会回退到完全不保留。
  • 4：错误。长度为 4 的真前缀是 ABAB，真后缀是 BABA，两者并不相同。
  • 5：错误。真前缀和真后缀都不能等于字符串本身；长度 5 属于完整字符串，不是真前缀。
复习

知识点详解

设模式串某个前缀为 S，前缀函数通常记录 S 的最长相等真前缀和真后缀长度。发生失配时，已经匹配的文本尾部如果与模式串开头相同，就可以把这部分直接对齐，避免重复比较。next 和 nextval 是对这种回退关系的不同表达或优化，但教材可能采用从 0 开始、从 1 开始以及初值为 -1 或 0 等不同约定。考试若直接要求数组值，必须先按题目给出的定义计算；若题目问“能保留多少个字符”，用最长相等前后缀判断通常最清楚。

备考速记

失配别从头，先找已匹配部分的最长相等头和尾。

KMP算法 在前缀函数场景中的作用

KMP算法在本题中的核心价值，是解决“模式串 P="ABABAC"。KMP 匹配过程中，前 5 个字符 ABABA 已经匹配成功，但在比较第 6 个字符 C 时发生失配。已匹配部分 ABABA 的最长相等真前缀和真后缀长度为（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 给出模式串，要求计算某一位置的前缀函数或 next 值。
  • 给出一次失配位置，判断模式串应回退到哪个字符继续比较。
  • 比较朴素匹配与 KMP，判断文本指针是否需要回退。
KMP算法 在软件设计师软考中的考法

软考选择题通常不会只考概念定义，还会把KMP算法放到前缀函数场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。

解题思路

这题我建议直接把两排字符串写出来。ABABA 从左边截，能得到 A、AB、ABA、ABAB；从右边截，能得到 A、BA、ABA、BABA。先看最长的 ABAB 和 BABA，不相同；再退一格，ABA 和 ABA 对上了，所以答案是 3。此时文本中最后三个字符不用重查，下一次可拿当前失配字符继续和模式串第 4 个字符 B 比较。

考点定位

KMP 的核心不是背一串 next 数字，而是找已匹配部分的最长相等真前缀和真后缀。该长度决定失配后还能保留多少个已经确认匹配的字符。

易错提醒

  • 把最长公共子串误当成最长相等前后缀，去字符串中间寻找匹配片段。
  • 不同教材采用的 next、nextval 下标和初值约定不同，却直接比较数组数字，不先确认定义。
  • 失配后同时回退文本指针和模式指针，失去了 KMP 利用既有匹配信息的意义。

备考提示

  • 先掌握前缀函数的含义，再去适应 next[0]=-1、next[1]=0 等不同教材记法。概念不变，数组下标约定可能不同。
  • 计算时逐字符记录当前最长相等前后缀长度，比最后一次性猜整个 next 数组更稳。

你可能还想了解

  • KMP 中最长相等真前缀和真后缀怎么找？
  • next 数组为什么会有 -1 和 0 两种开头？
  • KMP 失配后文本指针需要回退吗？
  • nextval 相比 next 数组优化了什么？

本文小结

ABABA 的最长相等真前缀和真后缀都是 ABA，长度为 3。KMP 失配后可保留这三个已经匹配的字符，只移动模式串继续比较；不同教材的 next 数值约定可能不同，但最长相等前后缀的判断逻辑不变。