KMP算法通过预处理构建next数组，使主串指针不回退，时间复杂度稳定为O(n+m)；next[i]表示p[0..i]的最长相等真前后缀长度，失配时指导模式串滑动位置，避免暴力法的重复比较。
KMP算法通过预处理模式串、构建next数组，在匹配过程中避免主串指针回退，将时间复杂度稳定控制在O(n + m)（n为主串长度，m为模式串长度），显著优于暴力法的O(n×m)。
理解 next 数组的核心作用
next[i] 表示模式串 p[0..i] 这个子串的最长相等真前后缀长度（前缀不包含自身，后缀也不包含自身）。它不是记录“能跳多远”，而是告诉失配时“模式串该对齐到哪个位置继续比”。
例如模式串 "ABABC"： - "A" → 无真前后缀 → next[0] = 0 - "AB" → 前缀"A"，后缀"B" → 不等 → next[1] = 0 - "ABA" → 前缀"A" = 后缀"A" → next[2] = 1 - "ABAB" → 前缀"AB" = 后缀"AB" → next[3] = 2 - "ABABC" → 前缀"AB" ≠ 后缀"BC"，"A" ≠ "C" → next[4] = 0 → next 数组为 [0, 0, 1, 2, 0]
构建 next 数组的实用写法
用双指针 j（前缀末尾）和 i（当前处理位置），递推计算，无需回溯主串：
- 初始化 next[0] = 0，j = 0
- i 从 1 开始遍历模式串
- 若 p[i] == p[j]，则 j++，next[i] = j
- 若不等且 j > 0，令 j = next[j−1] 继续尝试匹配
- 若不等且 j == 0，next[i] = 0
关键点：j 的回退不是乱跳，而是沿已知的最长公共前后缀链逐步收缩，确保不漏掉可能的重叠匹配。
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
KMP 主匹配过程的操作逻辑
主串指针 i 一路向前不回头，只靠调整模式串指针 j 来应对失配：
- 初始化 i = 0（主串），j = 0（模式串）
- 循环遍历主串每个字符 s[i]：
- 若 s[i] == p[j]，i 和 j 同时加 1
- 若不等且 j > 0，j = next[j−1]（利用已有信息滑动模式串）
- 若不等且 j == 0，仅 i++（模式串从头开始比）
- 一旦 j == m（模式串走完），说明匹配成功，返回起始位置 i − m
整个过程主串扫描一次，模式串内部跳转由 next 数组驱动，真正实现“不走回头路”。
为什么它比暴力法快？
暴力法失配后，主串指针要退回 i−j+1，再从头比——大量重复比较已验证过的字符。KMP 则通过 next 数组复用已匹配的前缀信息，让模式串尽可能右移，同时保证左端已比对部分仍与主串对齐。比如主串 "AAAAAB" 匹配 "AAAB"，暴力需比 4+4+4+4=16 次；KMP 因 next=[0,1,2,0]，失配后直接跳到第 3 位继续，总比较次数约 6–8 次。
