Z 算法

字符串

说明

计算每个位置与整个字符串的最长公共前缀；借助已知匹配区间实现 O(n)。

分析

Z[i] 表示从位置 i 开始的子串与整个字符串前缀相同的长度。维护当前最右匹配区间，可以先复用区间内已经计算的结果，再向外扩展。

图解推演

aabcaab 在下标 4 开始的 aab 与整个串前缀相同，故 Z[4]=3，匹配区间为 [4,7)。下标 5 落在区间内，可以先取 min(7−5,Z[1])=1，随后尝试向右扩展。复用长度必须受右边界限制，不能把前面已知的 Z 值无条件照搬。

查看图表代码

适用前提与边界

把“模式＋分隔符＋文本”拼接后，也能用 Z 值寻找所有匹配位置。

示例输入与调用

fmt.Println(ZValues("aabcaab"))

运行输出

[0 1 0 0 3 1 0]

完整 Go 示例

package main

import "fmt"

func ZValues(s string) []int {
	z := make([]int, len(s))
	l, r := 0, 0
	for i := 1; i < len(s); i++ {
		if i < r {
			z[i] = min(r-i, z[i-l])
		}
		for i+z[i] < len(s) && s[z[i]] == s[i+z[i]] {
			z[i]++
		}
		if i+z[i] > r {
			l, r = i, i+z[i]
		}
	}
	return z
}

func main() {
	fmt.Println(ZValues("aabcaab"))
}