LeetCode 3455. 最短匹配子字符串 — Go 实现可直接提交核心思路将 p 按 * 分割为 left * mid * right 三部分。用 KMP 分别找出三者在 s 中的所有匹配位置然后用双指针枚举 mid 的每个出现位置寻找最靠右的合法 left 和最靠左的合法 right使得子串长度最短。关键若某部分为空串则视为在 s 的每个位置包括末尾都匹配返回 [0, 1, ..., n]。---完整代码goimport (mathstrings)func shortestMatchingSubstring(s string, p string) int {// 1. 按 * 分割为三部分parts : strings.Split(p, *)left, mid, right : parts[0], parts[1], parts[2]// 2. KMP 找出所有匹配位置posL : kmpAll(s, left)posM : kmpAll(s, mid)posR : kmpAll(s, right)// 3. 双指针找最短匹配ans : math.MaxInt32j : 0 // posL 指针k : 0 // posR 指针for _, i2 : range posM {// left 必须在 mid 开始前结束i1 len(left) i2// 找满足条件的最后一个 left越靠右子串越短for j len(posL) posL[j]len(left) i2 {j}if j 0 {continue // 无合法 left}i1 : posL[j-1]// right 必须在 mid 结束后开始i3 i2 len(mid)// 找满足条件的第一个 right越靠左子串越短for k len(posR) posR[k] i2len(mid) {k}if k len(posR) {break // 后续 mid 更大不可能再有合法 right}i3 : posR[k]// 子串为 s[i1 : i3len(right)]length : i3 len(right) - i1if length ans {ans length}}if ans math.MaxInt32 {return -1}return ans}// kmpAll 返回 pattern 在 text 中所有匹配的起始位置// 若 pattern 为空返回 [0, 1, ..., len(text)]每个位置都匹配func kmpAll(text, pattern string) []int {if len(pattern) 0 {res : make([]int, len(text)1)for i : range res {res[i] i}return res}// 计算前缀函数 LPSm : len(pattern)lps : make([]int, m)j : 0for i : 1; i m; i {for j 0 pattern[i] ! pattern[j] {j lps[j-1]}if pattern[i] pattern[j] {jlps[i] j}}// KMP 匹配过程res : make([]int, 0)j 0for i : 0; i len(text); i {for j 0 text[i] ! pattern[j] {j lps[j-1]}if text[i] pattern[j] {j}if j m {res append(res, i-m1)j lps[j-1]}}return res}---复杂度分析指标 复杂度 说明时间 O(\|s\| \|p\|) KMP 线性扫描 双指针单调移动空间 O(\|s\| \|p\|) 存储 LPS 数组和匹配位置列表---关键边界测试输入 输出 说明sabaacbaecebce, pba*c*ce 8 常规匹配 baecebcesbaccbaadbc, pcc*baa*adb -1 无匹配sa, p** 0 空串匹配空 left/mid/rightsaa, paa** 2 leftaa, midrightsmadlogic, p*adlogi* 6 匹配 adlogi---为什么这样是对的1. KMP 找所有位置保证我们能枚举所有可能的匹配组合。2. 双指针单调性posL、posM、posR 都是升序数组。随着 mid 位置右移left 的最优位置只会右移或不变right 的最优位置也只会右移或不变。因此双指针均摊 O(N)。3. 空串处理kmpAll 对空 pattern 返回 [0..n]完美覆盖 p **、a**、**a 等边界情况无需额外特判。