跳转至

# Z 函数（扩展 KMP）

约定：字符串下标以 0 0 为起点．

## 定义

对于一个长度为 𝑛 n 的字符串 𝑠 s，定义函数 𝑧[𝑖]z[i] 表示 𝑠 s 和 𝑠[𝑖,𝑛 −1]s[i,n−1]（即以 𝑠[𝑖]s[i] 开头的后缀）的最长公共前缀（LCP）的长度，则 𝑧 z 被称为 𝑠 s 的 Z 函数．特别地，𝑧[0] =0 z[0]=0．

国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP（exKMP）．

这篇文章介绍在 𝑂(𝑛)O(n) 时间复杂度内计算 Z 函数的算法以及其各种应用．

## 解释

下面若干样例展示了对于不同字符串的 Z 函数：

- 𝑧(𝚊 𝚊 𝚊 𝚊 𝚊) =[0,4,3,2,1]z(aaaaa)=[0,4,3,2,1]
- 𝑧(𝚊 𝚊 𝚊 𝚋 𝚊 𝚊 𝚋) =[0,2,1,0,2,1,0]z(aaabaab)=[0,2,1,0,2,1,0]
- 𝑧(𝚊 𝚋 𝚊 𝚌 𝚊 𝚋 𝚊) =[0,0,1,0,3,0,1]z(abacaba)=[0,0,1,0,3,0,1]

## 朴素算法

Z 函数的朴素算法复杂度为 𝑂(𝑛 2)O(n 2)：

实现
C++Python

    1
    2
    3
    4
    5
    6
    7
    vector<int> z_function_trivial(string s) {
      int n = (int)s.length();
      vector<int> z(n);
      for (int i = 1; i < n; ++i)
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
      return z;
    }

    1
    2
    3
    4
    5
    6
    7
    def z_function_trivial(s):
        n = len(s)
        z = [0] * n
        for i in range(1, n):
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        return z

## 线性算法

如同大多数字符串主题所介绍的算法，其关键在于，运用自动机的思想寻找限制条件下的状态转移函数，使得可以借助之前的状态来加速计算新的状态．

在该算法中，我们从 1 1 到 𝑛 −1 n−1 顺次计算 𝑧[𝑖]z[i] 的值（𝑧[0] =0 z[0]=0）．在计算 𝑧[𝑖]z[i] 的过程中，我们会利用已经计算好的 𝑧[0],…,𝑧[𝑖 −1]z[0],…,z[i−1]．

对于 𝑖 i，我们称区间 [𝑖,𝑖 +𝑧[𝑖] −1][i,i+z[i]−1] 是 𝑖 i 的 匹配段，也可以叫 Z-box．

算法的过程中我们维护右端点最靠右的匹配段．为了方便，记作 [𝑙,𝑟][l,r]．根据定义，𝑠[𝑙,𝑟]s[l,r] 是 𝑠 s 的前缀．在计算 𝑧[𝑖]z[i] 时我们保证 𝑙 ≤𝑖 l≤i．初始时 𝑙 =𝑟 =0 l=r=0．

在计算 𝑧[𝑖]z[i] 的过程中：

- 如果 𝑖 ≤𝑟 i≤r，那么根据 [𝑙,𝑟][l,r] 的定义有 𝑠[𝑖,𝑟] =𝑠[𝑖 −𝑙,𝑟 −𝑙]s[i,r]=s[i−l,r−l]，因此 𝑧[𝑖] ≥m i n(𝑧[𝑖 −𝑙],𝑟 −𝑖 +1)z[i]≥min(z[i−l],r−i+1)．这时：
  - 若 𝑧[𝑖 −𝑙] <𝑟 −𝑖 +1 z[i−l]<r−i+1，则 𝑧[𝑖] =𝑧[𝑖 −𝑙]z[i]=z[i−l]．
  - 否则 𝑧[𝑖 −𝑙] ≥𝑟 −𝑖 +1 z[i−l]≥r−i+1，这时我们令 𝑧[𝑖] =𝑟 −𝑖 +1 z[i]=r−i+1，然后暴力枚举下一个字符扩展 𝑧[𝑖]z[i] 直到不能扩展为止．
- 如果 𝑖 >𝑟 i>r，那么我们直接按照朴素算法，从 𝑠[𝑖]s[i] 开始比较，暴力求出 𝑧[𝑖]z[i]．
- 在求出 𝑧[𝑖]z[i] 后，如果 𝑖 +𝑧[𝑖] −1 >𝑟 i+z[i]−1>r，我们就需要更新 [𝑙,𝑟][l,r]，即令 𝑙 =𝑖,𝑟 =𝑖 +𝑧[𝑖] −1 l=i,r=i+z[i]−1．

可以访问 这个网站 来看 Z 函数的模拟过程．

### 实现

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    vector<int> z_function(string s) {
      int n = (int)s.length();
      vector<int> z(n);
      for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r && z[i - l] < r - i + 1) {
          z[i] = z[i - l];
        } else {
          z[i] = max(0, r - i + 1);
          while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
      }
      return z;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    def z_function(s):
        n = len(s)
        z = [0] * n
        l, r = 0, 0
        for i in range(1, n):
            if i <= r and z[i - l] < r - i + 1:
                z[i] = z[i - l]
            else:
                z[i] = max(0, r - i + 1)
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
            if i + z[i] - 1 > r:
                l = i
                r = i + z[i] - 1
        return z

## 复杂度分析

对于内层 `while` 循环，每次执行都会使得 𝑟 r 向后移至少 1 1 位，而 𝑟 <𝑛 −1 r<n−1，所以总共只会执行 𝑛 n 次．

对于外层循环，只有一遍线性遍历．

总复杂度为 𝑂(𝑛)O(n)．

## 应用

我们现在来考虑在若干具体情况下 Z 函数的应用．

这些应用在很大程度上同 前缀函数 的应用类似．

### 匹配所有子串

为了避免混淆，我们将 𝑡 t 称作 文本，将 𝑝 p 称作 模式．所给出的问题是：寻找在文本 𝑡 t 中模式 𝑝 p 的所有出现（occurrence）．

为了解决该问题，我们构造一个新的字符串 𝑠 =𝑝 + ⋄ +𝑡 s=p+⋄+t，也即我们将 𝑝 p 和 𝑡 t 连接在一起，但是在中间放置了一个分割字符 ⋄⋄（我们将如此选取 ⋄⋄ 使得其必定不出现在 𝑝 p 和 𝑡 t 中）．

首先计算 𝑠 s 的 Z 函数．接下来，对于在区间 [0,|𝑡| −1][0,|t|−1] 中的任意 𝑖 i，我们考虑以 𝑡[𝑖]t[i] 为开头的后缀在 𝑠 s 中的 Z 函数值 𝑘 =𝑧[𝑖 +|𝑝| +1]k=z[i+|p|+1]．如果 𝑘 =|𝑝|k=|p|，那么我们知道有一个 𝑝 p 的出现位于 𝑡 t 的第 𝑖 i 个位置，否则没有 𝑝 p 的出现位于 𝑡 t 的第 𝑖 i 个位置．

其时间复杂度（同时也是其空间复杂度）为 𝑂(|𝑡| +|𝑝|)O(|t|+|p|)．

### 本质不同子串数

给定一个长度为 𝑛 n 的字符串 𝑠 s，计算 𝑠 s 的本质不同子串的数目．

考虑计算增量，即在知道当前 𝑠 s 的本质不同子串数的情况下，计算出在 𝑠 s 末尾添加一个字符后的本质不同子串数．

令 𝑘 k 为当前 𝑠 s 的本质不同子串数．我们添加一个新的字符 𝑐 c 至 𝑠 s 的末尾．显然，会出现一些以 𝑐 c 结尾的新的子串（以 𝑐 c 结尾且之前未出现过的子串）．

设串 𝑡 t 是 𝑠 +𝑐 s+c 的反串（反串指将原字符串的字符倒序排列形成的字符串）．我们的任务是计算有多少 𝑡 t 的前缀未在 𝑡 t 的其他地方出现．考虑计算 𝑡 t 的 Z 函数并找到其最大值 𝑧 m a x z max．则 𝑡 t 的长度小于等于 𝑧 m a x z max 的前缀的反串在 𝑠 s 中是已经出现过的以 𝑐 c 结尾的子串．

所以，将字符 𝑐 c 添加至 𝑠 s 后新出现的子串数目为 |𝑡| −𝑧 m a x|t|−z max．

算法时间复杂度为 𝑂(𝑛 2)O(n 2)．

值得注意的是，我们可以用同样的方法在 𝑂(𝑛)O(n) 时间内，重新计算在端点处添加一个字符或者删除一个字符（从尾或者头）后的本质不同子串数目．

### 字符串整周期

给定一个长度为 𝑛 n 的字符串 𝑠 s，找到其最短的整周期，即寻找一个最短的字符串 𝑡 t，使得 𝑠 s 可以被若干个 𝑡 t 拼接而成的字符串表示．

考虑计算 𝑠 s 的 Z 函数，则其整周期的长度为最小的 𝑛 n 的因数 𝑖 i，满足 𝑖 +𝑧[𝑖] =𝑛 i+z[i]=n．

该事实的证明同应用 前缀函数 的证明一样．

## 练习题目

- luogu P5410【模板】扩展 KMP/exKMP（Z 函数）
- luogu P7114【NOIP2020】字符串匹配
- CF126B Password
- UVa # 455 Periodic Strings
- UVa # 11022 String Factoring
- UVa 11475 - Extend to Palindrome
- Codechef - Chef and Strings
- Codeforces - Prefixes and Suffixes
- Leetcode 2223 - Sum of Scores of Built Strings

本页面主要译自博文 Z-функция строки и её вычисление 与其英文翻译版 Z-function and its calculation．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：sshwy, StudyingFather, Enter-tainer, LeoJacob, countercurrent-time, H-J-Granger, minghu6, NachtgeistW, iamtwz, Ir1d, Tiphereth-A, weiyong1024, AngelKitty, c-forrest, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, HeRaNO, Konano, LovelyBuggies, Makkiy, mgt, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, Xeonacid, amlhdsan, Dfkuaid, ethanrao, GavinZhengOI, Gesrua, gi-b716, ksyx, kxccc, lychees, Marcythm, Menci, ouuan, Peanut-Tang, pengxurui, shawlleyw, shuzhouliu, SukkaW, TrisolarisHD
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用