LeetCode 3455. 最短匹配子字符串 — Go 实现（可直接提交）
核心思路
将 `p` 按 `'*'` 分割为 `left * mid * right` 三部分。用 KMP 分别找出三者在 `s` 中的所有匹配位置，然后用双指针枚举 `mid` 的每个出现位置，寻找最靠右的合法 `left` 和最靠左的合法 `right`，使得子串长度最短。
关键：若某部分为空串，则视为在 `s` 的每个位置（包括末尾）都匹配，返回 `[0, 1, ..., n]`。
---
完整代码
```go
import (
"math"
"strings"
)
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.MaxInt32
j := 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] < i2+len(mid) {
k++
}
if k == len(posR) {
break // 后续 mid 更大，不可能再有合法 right
}
i3 := posR[k]
// 子串为 s[i1 : i3+len(right)]
length := i3 + len(right) - i1
if 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
}
// 计算前缀函数 LPS
m := len(pattern)
lps := make([]int, m)
j := 0
for i := 1; i < m; i++ {
for j > 0 && pattern[i] != pattern[j] {
j = lps[j-1]
}
if pattern[i] == pattern[j] {
j++
lps[i] = j
}
}
// KMP 匹配过程
res := make([]int, 0)
j = 0
for 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-m+1)
j = lps[j-1]
}
}
return res
}
```
---
复杂度分析
指标 复杂度 说明
时间 O(\|s\| + \|p\|) KMP 线性扫描 + 双指针单调移动
空间 O(\|s\| + \|p\|) 存储 LPS 数组和匹配位置列表
---
关键边界测试
输入 输出 说明
`s="abaacbaecebce", p="ba*c*ce"` `8` 常规匹配 `"baecebce"`
`s="baccbaadbc", p="cc*baa*adb"` `-1` 无匹配
`s="a", p="**"` `0` 空串匹配（空 left/mid/right）
`s="aa", p="aa**"` `2` `left="aa"`, `mid=right=""`
`s="madlogic", p="*adlogi*"` `6` 匹配 `"adlogi"`
---
为什么这样是对的？
1. KMP 找所有位置：保证我们能枚举所有可能的匹配组合。
2. 双指针单调性：`posL`、`posM`、`posR` 都是升序数组。随着 `mid` 位置右移，`left` 的最优位置只会右移或不变，`right` 的最优位置也只会右移或不变。因此双指针均摊 O(N)。
3. 空串处理：`kmpAll` 对空 pattern 返回 `[0..n]`，完美覆盖 `p = "**"`、`"a**"`、`"**a"` 等边界情况，无需额外特判。
