首页 📚学习笔记

Z函数

$\quad\quad$对于给定的两个字符串 $S,T$ ,长度分别为 $n,m$ 下标从 $0$ 开始。定义 $extend[i]$ 为 $S[i]\cdots S[n]$ 与 $T$ 的最长相同前缀的长度。$Z$ 函数即可在 $\mathcal O(n)$ 的复杂度内求出所有的 $extend$.

$\quad\quad$显然,暴力是 $\mathcal O(n^2)$ 的。

$\quad\quad$那为什么它又叫做扩展 $KMP$ 呢。因为当 $extend[i]=m$ 时,说明 $T$ 是 $S$ 的子串,并且他和 $KMP$ 都是利用之前的已知信息来推导的


算法流程

$\quad\quad$首先就像 $KMP$ 一样,我们要求出 $S$ 自己的 $extend$ 数组。

$\quad\quad$假设我们已知 $extend[j]\ (1\leq j \leq x)$,考虑如何求出 $extend[x]$

$\quad\quad$设当前已知 $extend$ 最大值为 $mx$ 且以 $h$ 为开头来匹配


若 $x+extend[x-h+1]\leq mx$

请输入图片描述

$\quad\quad$说明绿色部分全部相等,则直接$extend[x]=extend[x-h+1]$


若 $x+extend[x-h+1] > mx$

请输入图片描述

$\quad\quad$因为区域 $2,3$ 并不相等,可知,再盲目比较是没有意义的,所以只能 $extend[i]=mx-i$,并且更新 $h$ 的值

以上对于匹配两个不同的字符串同理


P5410 【模板】扩展 KMP(Z 函数)

代码实现




文章评论

目录