学习心得 - 字符串 - Manacher，KMP 及 Z 函数（扩展 KMP，exKMP）

ExFish · 2026-08-21 09:10:09 · 算法·理论

序

鉴于之前写文章时没有怎么写 KMP 的，这里也会一并记录一下 KMP 的学习笔记。这两个算法其实没啥太大的关系，但是又有差不多的工作原理。而 Z 函数倒是更类似于 Manacher 的算法。下面我会用尽可能容易理解的语言来讲解一下这两个字符串算法。之后我发现可以用 KMP 串起整个提高级字符串算法，因此写下此文。

此文可以用作提高级字符串全家桶学习笔记。

Manacher

由于 Manacher 的算法工作过程和 Z 函数基本是完全一致的，这里会用尽可能简单的语言稍微讲讲 Manacher。

Manacher 本质是一个均摊分析的暴力，从 \mathcal O(n^2) 降级成了 \mathcal O(n)，这就很厉害。其用于维护一个点为中心的最长扩张回文串长度。首先有一个问题就是回文串有奇有偶，我们将其同质化就是在相邻字符之间添加 #，首尾增加 < 与 > 表示开头与结束。然后我们考虑暴力。暴力可以直接枚举中心点，然后向左右两边贪心扩展，复杂度 \mathcal O(n^2)。稍微优一点的做法是二分哈希，但是时间复杂度仍然在 \mathcal O(n\log n)。

接下来就是 Manacher 的主要算法。其借助一个优化条件：回文中心对称。对于一个点 i 能扩展到的最长回文为 [i-p_i,i+p_i]，若其有 j\in [i,i+p_i]，则必有一个与其对称的 i-j'=j-i，所以 j'=2i-j，此时有范围 j'\in [i-p_i,i]。你会发现一个神奇的事情就是 j' 所对应的回文串只要没超过 [i-p_i,i+p_i]，那么就会在 j 处产生一样的回文串，也就是两组回文串关于 i 对称。此时我们就可以更新 p_j\leftarrow p_{j'=2i-j}。当然，还是要注意不能超过范围，则有 p_j=\min(p_{2i-j},i+p_i-j)。复杂度分析就是每个点最多只会被一个回文串拓展到，复杂度为 \mathcal O(n)。

那么这就是 Manacher 的全部内容，如果不理解可以看我的往期文章，或者私信 Ivan422。

KMP

既然要介绍 exKMP，首先你得先理解 KMP 是什么。KMP 是一种用于处理字符串内匹配的算法。还是首先考虑暴力，那么就是类似滑动窗口的匹配算法，哈希可以做到差不多 \mathcal O(|s|) 的复杂度（s 原始串（文本串），t 需要寻找的子串（模式串））。但是其常数和广为人知的卡法使得其的适应性不够强。我们考虑如何优化这个访问过程。

接下来我们要介绍一个东西叫做 Border，也叫做最长公共前后缀，如 \tt {\color{red}abc}d{\color{red}abc} 的 \tt border 就是 3，公共的前后缀就是 \tt\color{red} abc。我们从刚刚滑动窗口的思路去思考我们到底要找什么。现在有例子：

此时你发现：失配的位置永远算是一个后缀（从失配位置往后的所有都算作是失配）。那么此时你考虑如何移动。显然此时前面都是匹配清楚的。你会发现，不存在一个中间开始的值可以开始匹配，因为它一开始就断了匹配。那么此时我们就可以把前缀移动到失配的位置，看看能不能有更多的可能。因此，我们对模式串计算 \tt border，就可以快速匹配。

:::info[\tt border 数组]{open}

根据我刚刚的描述，你可能会认为 \tt border 只是一个数（整个字符串的 \tt border），但是为了方便一个位置失配后还能往回跳，我们定义 \tt border 数组为模式串一个前缀的最长公共前后缀。如下图，这个字符串的 \tt border 的情况：

注意：最长公共前后缀 \tt border 长度不能等于其本身（不然是个字符串长度都是其本身长度了，跳 Border 也没有任何意义）。

:::

我们先不考虑如何求 \tt border，而是先介绍如何直接在文本串上匹配。那么我们维护一个指针 j 表示当前匹配在模式串上的位置。注意之后的内容以及代码都是在 \texttt{0-index} 下描述的。如果 j=0 代表目前试图匹配最开头的字符。当 s_i\neq t_j 代表失配，那么此时就要往回退，此时 j={\tt border}_{j-1}，代表我们先暂且回退一位，从开头去尝试是否能匹配。不停尝试，直到匹配或者退回到 j=0。

:::warning[关于 Border 回退的写法区分]{open}

我查询了一些资料，这一段有非常多写法，有的是 s_{i}\neq t_{j+1} 代表下一位就要失配了，我们先不贸然行事，直接往回退就可以避免这一位的往回退（即此时 j 是已经匹配的位，而我们 \texttt{0-index} 的 j 是当前可能的匹配位置），有 j={\tt border}_{j}。这两者的区别会导致很多初学者不太理解这个（例如我 T.T）。

:::

此时，如果我们跳完 Border 了，那么有两种情况：啥都没找到，j=0。还有一种情况：匹配成功。若匹配成功我们就可以尝试匹配下一位，如果匹配失败说明这一位不配合，不管，因为从这个 i 位置开始应当是没出出息的。之后我们匹配完这一位后，可以有 i\to i+1，代表下一位的尝试。如果此时 j=|t|（注意 \texttt{0-index}）说明完全匹配了，我们直接跳到整个字符串的 \tt border，也就是 j={\tt border}_{j-1}（j=|t-1| 才是最后一位）。

这一段的编码其实不难，但是很难理解。这是我很久以前的一份代码，说的其实差不多都对，但是可能是从题解里稍微改了点，没有真正的理解。

j=0; // 再从头匹配
for(int i=0;i<a.size();i++){
    while(j>0&&a[i]!=b[j])j=bor[j-1]; // 开始真正的匹配, 失配, 跳过到可匹配点 
    if(a[i]==b[j])j++; // 模式串匹配成功, 更新 border 指针, 找到答案
    if(j==b.size()){cout<<i+1-b.size()+1<    <endl;j=bor[j-1];} // 正好匹配完, 输出位置, 但是要直接跳过
}   

那么我们考虑如何求模式串的最长公共前缀。你会发现最长公共前后缀的本质是什么：

设我们当前处理到黑色的部分，则其最长公共前后缀为下划线部分，本质是一个自己匹配自己的过程。这句话看起来很抽象，但是如果一个串的开头和结尾相同，则你可以复制一个完全一致的段贴到其结尾的部分，本质就是最长公共前后缀。然后还有一个问题：匹配自己需要 \tt border，但你还没求出来呢！注意，所需 \tt border 在之前一定已经求出来了，因为我们至多匹配到前缀的位置。

实现略微有点不一样，还是一样的 j=0，但是我们要从第 2 个位置开始匹配（i=1），不然从头匹配必然完全匹配，出现整串的 \tt border 与定义不符。此时从第二个位置开始匹配，代表最长可能后缀。j 也只是代表一个前缀位置指针而已。如果后缀失配那么只能让前缀往回走 j={\tt border}_{j-1}，代表先回到可能答案的位置，再找一个可能的前缀去试。如果匹配到了，那么就可以走到下一个位置了。由于这里是 \texttt{0-index}，所以此时走完下一个位置时 j 的整数值（不是其实际意义）的本质就是当前 i 长度模式串前缀的最长公共前后缀。这一点算是比较巧妙的设计吧，但是我当初没有领悟这一点。

代码和我说的是一样的，但是可能与大众的做法不一样。

j=0; // border 指针, 从头开始
for(int i=1;i<b.size();i++){
    while(j>0&&b[i]!=b[j])j=bor[j-1]; // 模式串失匹配, 跳过, 用上一位的, 跳过当前位置
    if(b[i]==b[j])j++; // 模式串匹配成功, 更新 border 指针
    bor[i]=j; // border 数组    
}

:::warning[关于 Border 记录方法的区分]{open}

同上，这里会稍微讲讲别的做法。有一种 \texttt{1-index} 的写法就是先将 j 跳到可能的前缀位置，但其失配位置仍然是 0，就可以保证在连开头都失配时回退到 0。但是 \texttt{0-index} 时因为技术原因所以只能保留一位 j=0 表示可能在 0 的位置有前缀。

总结一下区别吧：

你发现两处差（\tt index 与 j 意义的差别）使得其在记录 \tt border 下出现了巧妙的一致！

:::

最终会给一份我重构的带 \texttt{0-index} 与 \texttt{1-index} 的 KMP 在下面的代码框中。

:::success[KMP 模板代码]

使用说明：将 #define print_border 的注释删掉可以输出 Border，将 #define index 1 改成 #define index 0 可以切换为 _0_index_ 的运行方式，否则是 _1_index_ 运行。

#include<bits/stdc++.h>
using namespace std;

#define index 1
// #define print_border

namespace KMP{
    const int N=1e6+10;
    int n,m;
    int border[N]; // 最长公共前缀（有时也记作 next）
    // 0-index 的 KMP 写法
    void _0_index_(string s,string t){
        n=s.size();
        m=t.size();
        // t 自匹配部分
        int j=0; // border 指针
        #ifdef print_border
            cout<<"Border["<<0<<"] = "<<border[0]<<"\n";
        #endif
        for(int i=1;i<m;i++){
            while(j&&t[i]!=t[j]) j=border[j-1]; 
            if(t[i]==t[j]) ++j;
            border[i]=j;
            #ifdef print_border
                cout<<"Border["<<i<<"] = "<<border[i]<<"\n";
            #endif
        }
        // s 匹配 t 部分
        j=0; // border 指针
        for(int i=0;i<n;i++){
            while(j&&s[i]!=t[j]) j=border[j-1];
            if(s[i]==t[j]) ++j;
            if(j==m){ cout<<i+1-m+1<<"\n"; }
        }
        // 符合此题的输出，非必须
        for(int j=0;j<m;j++) cout<<border[j]<<" ";
    }
    // 1-index 的 KMP 写法
    void _1_index_(string s,string t){
        n=s.size();
        m=t.size();
        s=" "+s;
        t=" "+t;
        int j=0; // 注意这里的意义不一样了，这是已经匹配的位置
        // t 自匹配部分
        #ifdef print_border
            cout<<"Border["<<1<<"] = "<<border[1]<<"\n";
        #endif
        for(int i=2;i<=m;i++){
            while(j&&t[i]!=t[j+1]) j=border[j]; 
            if(t[i]==t[j+1]) ++j;
            border[i]=j;
            #ifdef print_border
                cout<<"Border["<<i<<"] = "<<border[i]<<"\n";
            #endif
        }        
        // s 匹配 t 部分
        j=0; // border 指针
        for(int i=1;i<=n;i++){
            while(j&&s[i]!=t[j+1]) j=border[j];
            if(s[i]==t[j+1]) ++j;
            if(j==m){ cout<<i-m+1<<"\n"; }
        }
        // 符合此题的输出，非必须
        for(int i=1;i<=m;i++) cout<<border[i]<<" ";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s,t;
    cin>>s>>t;
    if(index==0)
        KMP::_0_index_(s,t);
    else
        KMP::_1_index_(s,t);
    return 0;
}

:::

时间复杂度分析：因为跳 \tt border 这个东西衰减特别快，所以可以视为 \mathcal O(|s|+|t|)。

扩展 KMP / Z 函数 / exKMP

:::warning[关于代码的 \tt index 问题]{open}

为适应尽可能多的字符串问题，Z 函数一章如果没有解释，则全部字符串均为 \texttt{1-index}。

模板题中定义的 Z(1)=|t|，这个东西可能对代码的规律性有影响，所以特此定义 Z(1)=|t|（代码中也特殊钦定了）。当然如果不能包含整串的话你也可以认为 Z(1)=0。

:::

名字老多了！但是跟 KMP 一样让人难以理解，不知道为什么之前没有记过笔记。这个东西的功能很怪异，其能在 \mathcal O(|s|+|t|) 的时间复杂度处理出文本串 s 所有后缀与模式串 t 的最长公共前缀。好像很没用？是真的很没用。其算法原理比较复杂，但是由于其类似 Manacher，故与 Manacher 一起讲解。

为什么这个东西叫做 Z 函数呢？我们定义一个东西为 Z(i)，含义是模式串 t 以 t_i 开头的后缀（t[i,n]）的最长公共前缀的长度。举个例子吧！还是刚刚 KMP 的那个例子：

这个东西和 \tt border 还是有区别的，其不一定要是严格后缀，只是后缀的一小段前缀就可以了。然后我们考虑如何 \mathcal O(n) 计算这个东西。按照 i:1\to |t| 的顺序来计算。你发现问题类似从一个中心点 i 向右延申，然后对应的从 1 开始向右延申的最长匹配。这个东西有 \mathcal O(n^2) 的暴力，类似 Manacher 的暴力中心扩展法。那么我们考虑有没有类似的方法。直接暴力扩展复杂度太高了，但是我们是不是可以用均摊的方法，把复杂度降低到 \mathcal O(n)？

是可以的。我们考虑类似 Manacher 维护一个 i，设 z_i 为一个点最长合法延申范围。则当我们要更新 j，且这个 j 符合 j\le i+z_i，我们考虑转移对称方案。你发现，关于 i 的对称段是 [1,z_i+1] 与 [i,z_i+i] 相等。我们用对称的思路，就可以知道 j\in[i,z_i+i] 中，有一个与其对称的点 j'\in[1,z_i+1]。这个对称能带来对称的性质，你会发现有合法的扩展距离 z_{j'}\to z_j。根据推导，你会发现 j'-1=j-i，则 j'=j-i+1，有转移 z_{j-i+1}\to z_j。

然后根据 Manacher 的结论，我们发现 j+z_j 必须要 \le i+z_i，不然结论无法被保证。根据推导，我们有 z_j\le i-j+z_i，也就是 z_j=\min(z_{j-i+1},i+z_i-j)。因为我们要维护最大的 r=i+z_i-1，则转移一般写作 z_j=\min(z_{j-i+1},r-j+1)（因为 -1 所以要加回来）。时间复杂度也是类似的一个点最多被一个 LCP 覆盖，时间复杂度 \mathcal O(|t|)。

这一段的代码其实很简单：

void exKMP(string s,int n){
    int l=1,r=0;
    for(int i=1;i<=n;i++)
        Z[i]=0;
    Z[1]=n;
    for(int i=2;i<=n;i++){
        if(i>r)
            Z[i]=0;
        else{
            int k=i-l+1;
            Z[i]=min(Z[k],r-i+1);
        }
        while(i+Z[i]<=n&&s[Z[i]+1]==s[i+Z[i]])
            ++Z[i];
        if(i+Z[i]-1>r)
            l=i,
            r=i+Z[i]-1;
    }
}

但是问题来了，这个东西跟 KMP 有任何说明关系吗？到这里还没有，但是我们考虑怎么匹配。由于你发现这个模式串的 Z 函数预处理非常类似自己匹配自己，那么我们直接将其搬运到文本串上的匹配。还是 i:1\to |s| 的枚举，此时我们维护一个 p_i 表示 i 为匹配左端点能匹配到的最长公共前缀。还是一样的，我们考虑暴力的复杂度为 \mathcal O(|s||t|)，我们不喜欢这个时间复杂度，所以考虑如何用均摊的方式降低匹配。

一个合法的匹配就是 s[i,i+p_i]=t[1,1+p_i]，那么我们考虑类似的对称性。设目前我们要计算的是 p_j，若其 j>i+p_i，说明其没有被更新过，那么目前我们得不到任何信息用于继承。否则 j\in s[i,i+p_i]，我们可以找到一个对称点 j'\in t[1,1+p_i]。此时在 j' 这个位置的 z_{j'} 就可以派上用场了，这里 z_{j'} 的意义是 t[j',j'+z_{j'}]=t[1,1+z_{j'}]。我们要找的是 s[j,j+p_j]=t[1,1+p_j] 的最长前缀，显然 j\to j' 是对应的，所以我们有 p_j=z_{j'}。这个有点绕，稍微整理一下：

:::info[位置的具体关系]{open}

首先，根据定义我们可以有：

同理，我们能找到一个：

因为 j 是在 LCP 之中的：

所以我们可以得到：

同理根据字符串的对应关系，我们有：

这个 t 看起来很繁琐，但是 j 对应的 j'=j-i+1，有：

你发现 t[j',j'+x] 是一个很熟悉的形式，在 t 的 Z 函数中我们有：

此时设 x\le z_{j'}，且根据问题定义我们要最大化 x，则可以在合法范围内取到 x=z_{j'}，带入原式可以得到：

符合我们要的问题式，则得到 p_j=z_{j'}=z_{j-i+1}。

:::

那么我们得到了一个可能的最大化取值：p_j=z_{j-i+1}，之后我们考虑约束范围，显然 j+p_j 不能超过 i+p_i，即 p_j\le i+p_i-j，最终得出的 LCP 转移式子就是 p_{j}=\min(z_{j-i+1},i+p_i-j)。这个东西的时间复杂度也是差不多的，每个值最多被平推一次，则时间复杂度为 \mathcal O(|s|)。

void exKMP2(string s,int n,string t,int m){
    exKMP(t,m);
    int l=1,r=0;
    for(int i=1;i<=n;i++)
        p[i]=0;
    for(int i=1;i<=n;i++){
        if(i>r)
            p[i]=0;
        else{
            int k=i-l+1;
            p[i]=min(Z[k],r-i+1);
        }
        while(i+p[i]<=n&&t[p[i]+1]==s[i+p[i]])
            ++p[i];
        if(i+p[i]-1>r)
            l=i,
            r=i+p[i]-1;
    }
}

最终得到的答案就是 p_i，时间复杂度为 \mathcal O(|s|+|t|)，非常优秀。最后有一个问题还没有回答就是其和 KMP 的关系：只有外层结构有关。