扩展KMP(Z函数)详解

对于一个长度为n的字符串S。z[i] 表示S与其后缀S[i,n]的**最长公共前缀(LCP)**的长度。国外一般将计算该数组的算法称为，而国内则称其为扩展 KMP。下面介绍O(N)时间复杂度内求解Zfunc的方法。Manacher（马拉车）算法详解，原理分析-CSDN博客。

EQUINOX1

919人浏览 · 2024-07-27 18:05:27

EQUINOX1 · 2024-07-27 18:05:27 发布

一、Z Func

1.1 定义

对于一个长度为n的字符串S。z[i] 表示S与其后缀S[i,n]的**最长公共前缀(LCP)**的长度。

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

下面介绍O(N)时间复杂度内求解Zfunc的方法。

其计算方法和Manacher算法极为相似，详见：Manacher（马拉车）算法详解，原理分析-CSDN博客

1.2 暴力算法

std::vector<int> zFunction(const std::string s) {
    int n = s.size();
    std::vector<int> z(n);
    for (int i = 0 ; i < n; ++ i) 
		while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++ z[i];
    return z;
}

1.3 线性算法

1.3.1 Z-box

类似 Manacher 算法的加速盒子，Zfunc 的线性算法也有一个盒子，为当前最靠右的匹配后缀，我们称之为 Z-box。

通常用指针[l, r]代表Z-box的左右边界，个人喜欢维护Z-box的起始指针 j，右边界可以通过j + z[j] 获得。

1.3.2 算法流程

当前 Z-box 左端点为 j，需要计算z[i] 的值
如果 i 在 [j, j + z[i]) 内，那么我们可以用 i 在 [j, j + z[i]) 的相对位置，计算出前缀的对应位置 k = i - j

那么我们可以利用前缀与Z-box的匹配计算出盒内的z 值

z[i] = std::min(j + z[j] - i, z[i - j]);，二者取min是因为我们只能计算盒内部分
对于盒外部分，暴力扩展：

while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++ z[i];
计算完毕后，如果i + z[i] > j + z[j]，则说明要更新Z-box

1.3.3 复杂度分析

对于内层 while 循环，如果成功扩展，一定会在后面更新j（因为如果不扩展，说明i + z[i] 根本没有到达盒子右边界）

而右边界最多移动到 n ，所以while的整体时间复杂度是O(N)

因而我们算法整体时间复杂度为O(N)

1.3.4 代码实现

std::vector<int> zFunction(const std::string s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;

    for (int i = 1, j = 1; i < n; ++ i) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++ z[i];
        if (i + z[i] > j + z[j])
            j = i;
    }

    return z;
}

二、OJ练习

2.1 模板

原题链接

P5410 【模板】扩展 KMP/exKMP（Z 函数） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

zFunc计算部分就不说了，我们如何线性求p[]？

类似zFunc 的计算，我们维护一个p-Box，代表字符串 a 的最右匹配后缀

那么同样的，盒内转移，盒外暴力扩展即可

时间复杂度：O(N)

注意开long long

AC代码

#include <bits/stdc++.h>
#include <ranges>
// #define DEBUG
using i64 = long long;

std::vector<int> zFunction(const std::string& s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; ++ i) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++ z[i];
        if (i + z[i] > j + z[j]) j = i;
    }
    return z;
}

void solve()
{
    std::string a, b;
    std::cin >> a >> b;
    std::vector<int> z = zFunction(b);
    i64 s = 0;
    int n = a.size(), m = b.size();

    for (int i = 0; i < m; ++ i) s ^= (z[i] + 1LL) * (i + 1);
    std::cout << s << '\n';
    
    std::vector<int> p(n + 1);
    s = 0;

    for (int i = 0, j = 0; i < n; ++ i) {
        p[i] = std::max(0, std::min(j + p[j] - i, z[i - j]));
        while (i + p[i] < n && p[i] < m && a[i + p[i]] == b[p[i]]) ++ p[i];
        if (i + p[i] > j + p[j]) j = i;
    }

    for (int i = 0; i < n; ++ i) s ^= (p[i] + 1LL) * (i + 1);
    std::cout << s;
}

int main()
{
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_--)
        solve();
    return 0;
}

2.2 Password

原题链接

CF126B Password

思路分析

很简单，如果答案存在那么它是一个后缀，那么z[i] = n - i

然后只需判断中间是否出现过即可

AC代码

#include <bits/stdc++.h>
#include <ranges>
#define sc scanf
// #define DEBUG
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using PII = std::pair<int, int>;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1e18 + 7;
constexpr int P = 1E9 + 7;
constexpr double eps = 1E-6;

std::vector<int> zFunction(const std::string& s) {
    int n = s.size();
    std::vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; ++ i) {
        z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++ z[i];
        if (i + z[i] > j + z[j]) j = i;
    }
    return z;
}

void solve()
{
    std::string s;
    std::cin >> s;
    auto z = zFunction(s);
    int n = s.size();
    std::vector<int> cnt(n + 2);
    int ma = 0, res = 0;
    for (int i = 1; i < n; ++ i) {
        if (z[i] == n - i && (cnt[z[i]] || z[i] < ma))
            res = std::max(res, z[i]);
        ++ cnt[z[i]];   
        ma = std::max(ma, z[i]);
    }
    
    if (res) std::cout << s.substr(0, res);
    else std::cout << "Just a legend";
}

int main()
{
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_--)
        solve();
    return 0;
}

2.3 F - Concat (2nd)

[补档]2026.01.16

原题链接

F - Concat (2nd)

思路分析

不难想到字典序最小就是把S[] 按照 S[i] + S[j] < S[j] + S[i] 排序（证明使用微扰法即可）

然后A[2] 肯定是由A[1] 交换了一对下标得到，一般地，我们考虑 S[i] 如果和S[j]交换**(注意这里取i < j)**，那么j 取 i + 1 得到的肯定字典序最小

如果存在 S[i] + S[i + 1] == S[i + 1] + S[i]，那么直接输出A[1]即可

否则，A[2] 应由交换某个(S[i], S[i+1]) 得到，但是检查[0, N - 2] 妥妥超时，我们发现，由于此时任意S[i] + S[i + 1] != S[i + 1] + S[i]，所以我们如果定义 T[i] 为A[1] 交换 S[i], S[i+1] 所得，那么任意 i < N - 3，有 T[i] < T[N - 2] (考虑字符串前缀字典序即可)

但是T[N - 2] 和 T[N - 3] 的大小关系是无法确定的，比如 “a”, “aab”, “b”，T[N - 3] < T[N - 2]

而 “a", “ad”, “c” 有T[N-2] < T[N-3]

所以排完序比较 T[N - 2] 和 T[N - 3] 即可

但是，如果排序的时候直接利用 s + t < t + s，即创建两个字符串然后比较的话，单次比较是 O(|s| + |t|)的，这样我们可以构造出TLE的样例，如：

N = 1E5，S[0] = string(5E5, ‘a’)，然后任意N - 1个互不相同的字符串，由于排序基于快速排序（当然，如python那样的Tim排序也会被下面的情形卡掉），那么在第一次快速划分的时候，如果 S[0] 被选为pivot，那么要进行N次比较，每次O(5E5)，这次快速划分就达到了 5E10量级。

但是我们如果将 s + t < t + s 的比较降低到O(min(|s|, |t|))，那么最坏情况下 max(|s[i]|) = sqrt(1E6)时，我们的复杂度也不过是 Σ|si| logN

如何加速？—— ZFunc

对于s，t(|s| > |t|, |s| = n, |t| = m，s 的Z函数为zs[]，zt[] 同理)，我们先比较前n 个元素，如果还不够，我们看 zs[m]和n-m的关系，如果zs[m] < n - m，我们比较 s[m + zs[m]] 和 s[zs[m]] 即可

否则，我们只需比较 t 和 s[n-m, n)

单次比较时间复杂度为 O(min(|s|, |t|))

另解：利用字符串哈希+二分求lcp来加速s + t 和 t + s 的比较，具体代码见代码二

AC代码(C#)

代码一（ZFunction）

public void Solve() {
    int N = br.ReadInt32();
    string[] s = new string[N];
    int[][] z = new int[N][];
    for (int i = 0; i < N; ++i) {
        s[i] = br.ReadString();
        z[i] = ZFunction(s[i]);
    }
    var p = Enumerable.Range(0, N).ToArray();
    Array.Sort(p, (i, j) => {
        int sgn = 1;
        if (s[i].Length < s[j].Length) {
            (i, j) = (j, i);
            sgn = -1;
        }
        int n = s[i].Length, m = s[j].Length;
        for (int k = 0; k < m; ++k) {
            if (s[i][k] != s[j][k]) return sgn * s[i][k].CompareTo(s[j][k]);
        }
        if (n > m) {
            if (z[i][m] != n - m) {
                return sgn * s[i][z[i][m] + m].CompareTo(s[i][z[i][m]]);
            }
        }
        for (int k = 0; k < m; ++k) {
            if (s[j][k] != s[i][n - m + k]) return sgn * s[j][k].CompareTo(s[i][n - m + k]);
        }
        return 0;
    });
    string ans = string.Join("", p.Select(i => s[i]));
    if (N == 2) {
        bw.AppendLine(s[p[1]] + s[p[0]]);
        return;
    }
    for (int i = 0; i + 1 < N; ++i) {
        if (s[p[i + 1]] + s[p[i]] == s[p[i]] + s[p[i + 1]]) {
            bw.AppendLine(ans);
            return;
        }
    }
    StringBuilder a = new(), b = new();
    for (int i = 0; i < N - 3; ++i) {
        a.Append(s[p[i]]);
        b.Append(s[p[i]]);
    }
    a.Append(s[p[^2]]);a.Append(s[p[^3]]);a.Append(s[p[^1]]);
    b.Append(s[p[^3]]);b.Append(s[p[^1]]);b.Append(s[p[^2]]);
    string sa = a.ToString(), sb = b.ToString();
    bw.AppendLine(sa.CompareTo(sb) < 0 ? sa : sb);

    int[] ZFunction(string s) {
        int n = s.Length;
        int[] z = new int[n + 1];
        z[0] = n;
        for (int i = 1, j = 1; i < n; ++i) {
            z[i] = Math.Max(0, Math.Min(z[i - j], j + z[j] - i));
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
            if (i + z[i] > j + z[j]) j = i;
        }
        return z;
    }
}

代码二(字符串哈希)

public class SolutionA {
    public void Solve() {
        int N = br.ReadInt32();
        string[] s = new string[N];
        StringHash[] h = new StringHash[N];
        for (int i = 0; i < N; ++i) {
            s[i] = br.ReadString();
            h[i] = new(s[i]);
        }
        var p = Enumerable.Range(0, N).ToArray();
        Array.Sort(p, (i, j) => {
            int sgn = 1;
            if (s[i].Length < s[j].Length) {
                (i, j) = (j, i);
                sgn = -1;
            }
            int n = s[i].Length, m = s[j].Length;
            int lcp = Lcp(i, 0, j, 0, m);
            if (lcp < m) {
                return sgn * s[i][lcp].CompareTo(s[j][lcp]);
            }
            if (n > m) {
                lcp = Lcp(i, m, i, 0, n - m);
                if (lcp < n - m) {
                    return sgn * s[i][m + lcp].CompareTo(s[i][lcp]);
                }
                lcp = Lcp(j, 0, i, n - m, m);
                if (lcp < m) {
                    return sgn * s[j][lcp].CompareTo(s[i][n - m + lcp]);
                }
            }
            return 0;
        });
        int Lcp(int i, int sti, int j, int stj, int n) {
            int lo = 0, hi = n;
            while (lo < hi) {
                int x = (lo + hi + 1) / 2;
                if (h[i][sti, sti + x] == h[j][stj, stj + x]) {
                    lo = x;
                } else {
                    hi = x - 1;
                }
            }
            return lo;
        }
        string ans = string.Join("", p.Select(i => s[i]));
        if (N == 2) {
            bw.AppendLine(s[p[1]] + s[p[0]]);
            return;
        }
        for (int i = 0; i + 1 < N; ++i) {
            if (s[p[i + 1]] + s[p[i]] == s[p[i]] + s[p[i + 1]]) {
                bw.AppendLine(ans);
                return;
            }
        }
        StringBuilder a = new(), b = new();
        for (int i = 0; i < N - 3; ++i) {
            a.Append(s[p[i]]);
            b.Append(s[p[i]]);
        }
        a.Append(s[p[^2]]); a.Append(s[p[^3]]); a.Append(s[p[^1]]);
        b.Append(s[p[^3]]); b.Append(s[p[^1]]); b.Append(s[p[^2]]);
        string sa = a.ToString(), sb = b.ToString();
        bw.AppendLine(sa.CompareTo(sb) < 0 ? sa : sb);
    }

开源鸿蒙跨平台开发者社区

开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。

更多推荐

【Flutter for OpenHarmony第三方库】Flutter for OpenHarmony 离线模式实现指南

离线模式的实现需要建立在前端、存储层和网络层的协同工作基础之上。整体架构采用分层设计理念，将功能模块划分为网络监测层、数据缓存层、状态管理层和UI展示层四个核心层次。网络监测层负责实时感知网络状态的变化，包括网络连接、断开、类型切换等事件。该层通过监听系统网络事件，及时将网络状态同步给上层模块，为离线模式的切换提供决策依据。数据缓存层是离线模式的核心支撑，负责数据的本地持久化存储。根据数据特点的不

开源鸿蒙跨平台开发者社区

【Flutter for OpenHarmony第三方库】Flutter for OpenHarmony 离线模式实现：让你的应用无网也能萌萌哒~

用 Preferences 和 RelationalStore 实现数据缓存用 connection 模块监听网络状态设计温柔的离线提示 UI实现离线操作的同步队列有了离线模式，你的应用就像一个贴心的小伙伴，无论有网没网，都会陪伴在用户身边~希望这篇教程对你有帮助！有问题的话，欢迎在评论区留言讨论哦~