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"` 等边界情况，无需额外特判。