KMP：从 LPS 到主串不回退

LC28 的表面任务很简单：在长字符串haystack 中，找到短字符串needle 第一次完整出现的起始下标。

一次匹配已经成功了很多字符，最后却失配时，前面的成功信息能不能继续利用？

暴力匹配的回答是：不能。更换起点以后，从needle[0]重新开始。KMP 的回答是：能。它先分析模式串自身，把可复用的信息记录在lps中；失配时不让主串指针回头，只把模式串移动到下一个仍可能成功的位置。

1. 1lps[i] 保存了什么信息？
2. 2失配时为什么执行 j = lps[j-1]，而主串指针 i 不动？

给定两个字符串 haystack 和needle，请在主串中找出模式串第一次完整出现的起始下标。 下标从 0 开始；如果不存在完整匹配，返回 -1。

haystack := "sadbutsad"
needle := "sad"
// 输出：0

haystack := "leetcode"
needle := "leeto"
// 输出：-1

匹配阶段不断比较：

haystack[i] == needle[j]

• •i 指向主串当前待处理的字符。
• •j 指向模式串当前待匹配的字符，也表示已经连续匹配成功的字符数。
• •当 j == len(needle) 时，整个模式串已经匹配完成。
• •此时 i 在匹配区间后一位，所以起点是 i - j。

最直接的办法是枚举 haystack中每一个可能的起点。每选一个起点，就让needle 从下标 0 开始逐字符比较。

1func bruteStrStr(haystack, needle string) int {2    for start := 0; start+len(needle) <= len(haystack); start++ {3        j := 04        for j < len(needle) && haystack[start+j] == needle[j] {5            j++6        }7        if j == len(needle) {8            return start9        }10    }11    return -112}

这段代码完全正确，很适合确认题意。问题不是“会算错”，而是接近结尾才失配时， 下一轮会丢掉上一轮已经确认的前缀信息。

相等                    → i++，j++
失配且 j > 0          → j = lps[j-1]
失配且 j == 0         → i++
j == len(needle)       → return i - j

这四个分支里，真正抽象的是j = lps[j-1]。要理解它，必须先把 LPS 讲清楚。

lps[i] 表示模式串前缀子串pattern[0:i+1]中，最长的、同时作为真前缀和真后缀出现的字符串长度。

什么是真前缀和真后缀

以 "aabaa" 为例。真前缀包括a / aa / aab / aaba，真后缀包括a / aa / baa / abaa。 两组中最长的相等项是 aa，长度为 2，所以：

// pattern[0:5] == "aabaa"
lps[4] = 2

“真”表示不能等于整个字符串本身。否则任何字符串都能把自己同时当作前缀和后缀， 这个信息没有意义。

完整 LPS 示例

对于 pattern := "aabaaf"，最终得到：

lps := []int{0, 1, 0, 1, 2, 0}

• •lps[0] = 0："a" 没有非空真前后缀。
• •lps[1] = 1："aa" 的最长相等真前后缀是 "a"。
• •lps[2] = 0："aab" 不存在非空相等真前后缀。
• •lps[3] = 1："aaba" 的最长相等真前后缀是 "a"。
• •lps[4] = 2："aabaa" 的最长相等真前后缀是 "aa"。
• •lps[5] = 0："aabaaf" 不存在非空相等真前后缀。

构建阶段维护两个变量：i 表示当前正在确定lps[i]，length 表示当前候选的最长相等前后缀长度。

length++
lps[i] = length
i++

length = lps[length-1]

lps[i] = 0
i++

假设已经成功匹配了 needle[:j] == "aabaa"， 接下来发生失配。这段已匹配内容的最长相等真前后缀是aa，长度为 2。

已匹配区间末尾的 aa 已经与主串确认相等， 又与模式串开头的 aa 相同。因此不需要让主串回去重新确认， 只需把模式串指针调整为：

j = lps[j-1] // 5 → 2

为什么读取 lps[j-1]

失配发生在 needle[j]，真正成功的区间是needle[0:j]，最后一个成功下标是j-1。失配字符不能被包含在可复用信息中。

为什么不会漏掉答案

KMP 跳过的起点不是凭猜测判定失败。若被跳过的起点可能成功， 已匹配区间末尾就必须等于模式串相应前缀；LPS 已经保留了其中最长的合法候选。 不满足该结构的起点已经能被证明不可能。

haystack := "aabaacaabaaf"
needle := "aabaaf"
lps := []int{0, 1, 0, 1, 2, 0}

1. 1前五个字符 "aabaa" 连续匹配成功。
2. 2haystack[5]=='c' 与 needle[5]=='f' 失配。
3. 3j 根据 LPS 依次从 5 回退到 2、1、0，i 始终保持 5。
4. 4j==0 时仍失配，i 才从 5 前进到 6。
5. 5从主串下标 6 开始完整匹配，返回 6。

逐帧观察失配后的三次回退：j: 5 → 2 → 1 → 0。在整个过程中i == 5，直到 j 已经为 0 且仍然失配，i 才前进。

KMP 的匹配循环只有四个语义分支：

i++
j++

j = lps[j-1]

i++

return i - j

func strStr(haystack, needle string) int {    lps := buildLPS(needle)    i, j := 0, 0    for i < len(haystack) {        if haystack[i] == needle[j] {            i++            j++            if j == len(needle) {                return i - j            }        } else if j > 0 {            j = lps[j-1]        } else {            i++        }    }    return -1}

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }

    lps := buildLPS(needle)
    i, j := 0, 0

    for i < len(haystack) {
        if haystack[i] == needle[j] {
            i++
            j++
            if j == len(needle) {
                return i - j
            }
        } else if j > 0 {
            j = lps[j-1]
        } else {
            i++
        }
    }

    return -1
}

func buildLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1

    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else if length > 0 {
            length = lps[length-1]
        } else {
            lps[i] = 0
            i++
        }
    }

    return lps
}

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }

    lps := buildLPS(needle)
    i, j := 0, 0

    for i < len(haystack) {
        if haystack[i] == needle[j] {
            i++
            j++
            if j == len(needle) {
                return i - j
            }
        } else if j > 0 {
            j = lps[j-1]
        } else {
            i++
        }
    }

    return -1
}

func buildLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1

    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else if length > 0 {
            length = lps[length-1]
        } else {
            lps[i] = 0
            i++
        }
    }

    return lps
}

一组最小测试

func main() {
    println(strStr("sadbutsad", "sad"))          // 0
    println(strStr("leetcode", "leeto"))        // -1
    println(strStr("aabaacaabaaf", "aabaaf"))  // 6
    println(strStr("hello", "ll"))              // 2
    println(strStr("aaaaa", "bba"))             // -1
}

匹配阶段的不变量

haystack[i-j:i] == needle[0:j]

进入每次循环时，主串中紧靠 i 左侧的 j 个字符，已经与模式串前 j 个字符相等。失配时，LPS 告诉我们哪个已匹配后缀仍可充当前缀； 回退 j 后不变量继续成立，所以 i 无需回退。

虽然 j 会回退，但每次回退都会缩短候选前缀；i 只向右移动，不会回头。

1. 1题目要求寻找 needle 在 haystack 中第一次完整出现的位置。
2. 2暴力法失配后换起点并从头比较，会丢失已经确认的信息。
3. 3lps[i] 记录模式串前缀子串的最长相等真前后缀长度。
4. 4失配且 j>0 时，已匹配区间的后缀可以复用，因此执行 j=lps[j-1]。
5. 5主串指针 i 不回退，所以总复杂度从 O(n·m) 降为 O(n+m)。