KMP next 数组

数据结构

所属模块：DS-1/2 线性结构（线性表、栈、队列、数组、串） · 本模块第 15 / 15 个概念

在「DS-1/2 线性结构（线性表、栈、队列、数组、串）」概念体系中的位置

flowchart TD
    A["一对一的线性关系"] --> B["顺序存储：顺序表<br/>随机访问 O(1) / 插删 O(n)"]
    A --> C["链式存储：链表<br/>定位 O(n) / 插删 O(1)"]
    C --> C1["单链表 / 双链表 / 循环链表 / 静态链表"]
    A --> D["限制操作位置"]
    D --> E["栈 LIFO：括号匹配 / 表达式求值 / 递归"]
    D --> F["队列 FIFO：循环队列 / 双端队列 / BFS"]
    A --> G["数组：特殊矩阵压缩存储"]
    A --> H["串：朴素匹配 → KMP"]

核心概念：

概念	要点	易考点
时间/空间复杂度	基本语句频度关于 $n$ 的阶	循环主体计数、递归展开； $O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)$
头结点	单链表带头结点时，空表判断、首元操作与中间位置操作写法统一	408 代码题默认“带头结点”，读题先确认
循环队列	数组首尾相接；判空 `front==rear`，判满 `(rear+1)%n==front`（牺牲一个单元）	指针定义每题不同：2011-3（rear 指队尾元素）、2014-3（end2 指队尾后一个位置）——严格按题面定义
双端队列	两端均可入出	输出受限/输入受限变体的合法序列判断
出栈序列	入栈序 $1..n$ 时合法出栈序列数 = 卡特兰数 $\frac{1}{n+1}\binom{2n}{n}$	给定部分位置推可能取值（2013-2： $p_2=3$ 时 $p_3$ 的可能个数）；“入栈序确定不能确定出栈序”（2017-2 III 错误）
KMP next 数组	next[j] = 模式串前 $j$ 个字符中最长相等前后缀的长度 + 1（408 常用定义）	失配时主串指针 i 不回退，只退 j（2015-8：i=j=5 失配 → i=5, j=2）