KMP 字符串匹配

字符串

说明

失配时用前缀函数跳过已知相同的部分；时间 O(n+m)。

分析

先为模式串计算前缀函数 pi，记录每个前缀的最长真前后缀。文本匹配失配时，不必退回文本指针，只把模式指针跳到 pi 指定的位置。

图解推演

正文 ASCII 例子在文本 ababcabc 中查找 abc：已匹配 ab 后遇到 a≠c，按 pi[1]=0 回退模式指针，文本下标 2 不回退，并重新匹配 a，随后命中下标 2。若模式存在长边界，回退可保留那部分匹配；本例 pi 全零只展示最简单情形。

查看图表代码

适用前提与边界

预处理和搜索各为线性时间；示例逐字节比较并返回字节下标，可以查找多字节 UTF-8 模式。例如 KMP("你好Go", "好") 返回 3，查找 "Go" 返回 6。字节匹配不进行 Unicode 规范化，也不把结果换算为可见字符序号。

示例输入与调用

fmt.Println(KMP("ababcabc", "abc"))

运行输出

2

完整 Go 示例

package main

import "fmt"

func KMP(text, pattern string) int {
	if len(pattern) == 0 {
		return 0
	}
	pi := make([]int, len(pattern))
	for i := 1; i < len(pattern); i++ {
		j := pi[i-1]
		for j > 0 && pattern[i] != pattern[j] {
			j = pi[j-1]
		}
		if pattern[i] == pattern[j] {
			j++
		}
		pi[i] = j
	}
	j := 0
	for i := 0; i < len(text); i++ {
		for j > 0 && text[i] != pattern[j] {
			j = pi[j-1]
		}
		if text[i] == pattern[j] {
			j++
		}
		if j == len(pattern) {
			return i - j + 1
		}
	}
	return -1
}

func main() {
	fmt.Println(KMP("ababcabc", "abc"))
}