「学习笔记」KMP

InfiniteRobin · 2024-08-31 16:25:31 · 算法·理论

前缀函数及 KMP 算法

Part 1: 前缀函数

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。

举个十分简单的例子：s=\texttt{ababxyzabab}，其 border 为：\texttt{abab}。

注：本文中字符串的下标均从 0 开始。
注：|s| 表示字符串 s 的长度。
注：s(i,j) 表示字符串 s 的子串 s[i \ldots j]。例：s=\texttt{abcd}，s(0,1)=\texttt{ab}。

定义：Next(i)，即，对于整数 0 \le i < |s|，子串 s(0,i) 的 border 长。

前缀函数 即为获取 Next 数组的函数。

\texttt{Analysis}

我们先来模拟一下过程。

现在有字符串 s=\texttt{\color{BLUE}{abab}\color{BLACK}{xyz}\color{BLUE}{abab}\color{RED}{a}}，现在遍历到 i=11 即标红的那一位，要求 Next(i) 的值。

蓝色的为当前的 border。

我们知道，Next(i) 的值最多就只能在原有的基础上增加 1，于是我们就可以判断一下当前这一位能否构成更长的 border，也就是判断 border 的下一位是否与之匹配。

那么 border 的下一位怎么表示呢？我们知道，当前的 border 长就是 Next(i-1)，由于字符串下标是由 0 开始的，所以 border 的下一位，也就是 s[Next(i-1)] 啦！

如果 s[i]=s[Next(i-1)]，那么很简单，直接在当前 border 的长度上加一即可，也就是 Next(i)=Next(i-1)+1。
那如果不匹配，我们就只能看一下有没有一个更小的 border 长度 j，能够和当前的字符匹配上。
例如，我们这里可以找到 j=2，找到的 border 为 \texttt{ab}，并且它的下一位刚好和当前字符相等，那么，Next(i)=j+1。现在的思路就很清晰了，就只需要不断地找到更小的 j，直到 j=0 或匹配上即可。
那怎么获得 j 的值呢？

以下为关键部分。

首先我们要找到仅次于 Next(i) 的 j。
因为 j 一定需要满足 border 的条件，所以：
s(0,j-1)=s(i-j,i-1)。
同样地，由于这一段更小的 border 一定是由原来的那段大 border 中取出来的，因此，它也一定满足原 border 中的性质：
s(0,j-1)=s(i-j,i-1)=s(Next[i]-j,Next[i]-1)。
我们从中取出最重要的两部分：
s(0,j-1)=s(Next[i]-j,Next[i]-1)。
例子：
带回式子中，就是红色部分与蓝色部分相等：$\texttt{\color{RED}{ab}\color{BLUE}{ab}\color{BLACK}{xyzabab}}$。诶！我们定睛一看，这不就是原 border 中的小 border 吗！于是，我们就可以得到以下规律： $$j=Next(Next(i-1))。$$ 那么，若要找更小的 $j_{2}$，根据我们刚刚得到的公式： $$j_{2}=Next(j-1)。$$

\texttt{Code}

最后展示代码！

int Next[1000005];

void get_next(){
    for(int i=1;i<m;i++){ //m 是字符串长度
        int j=Next[i-1]; //初始为最大的 border 长
        while(j>0 && t[i]!=t[j]){ //j!=0 或 不匹配
            j=Next[j-1]; //不断找更小的 j
        }
        if(t[i]==t[j]){ //如果找到，当前答案就是原来答案 +1
            j++;
        }
        Next[i]=j;
    }
}

例题：P9606 [CERC2019] ABB

题目大意：求使给定小写字母字符串成为回文串需在字符串末尾加入字母的最少数量。

分析如下：

我们知道题目要求找出最大的后缀回文串。

我们考虑使用前缀函数解决问题。
由于回文串正着和反转后都是一样的，那么我们可以将 a 反转为 b。我们知道若 a 中存在一个后缀回文串，那么这个回文串必然出现在 b 的前缀。

那么问题转化为求 s=b+a 的 border。

用模板解决即可（别忘了开两倍空间）。

小技巧：在 a 和 b 中间插入一个特殊字符即可避免答案出现负数。

代码如下：

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

int n,Next[800005];
string s;

void get_next(){
    for(int i=1;i<=n*2;i++){
        int j=Next[i-1];
        while(j>0 && s[i]!=s[j]){
            j=Next[j-1];
        }
        if(s[i]==s[j]){
            j++;
        }
        Next[i]=j;
    }
}

void init(){
    string ss;
    cin>>n>>ss;
    s=ss;
    reverse(ss.begin(),ss.end());
    s=ss+"&"+s;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init();
    get_next();

    cout<<n-Next[n*2];
    return 0;
}

Part 2: KMP 算法

KMP 算法，其实就是对于前缀函数的一个应用。

这个算法解决的问题很简单：给你两个字符串 s,t，求 t 在 s 中出现的位置。

我们搞两个指针，指向 t 和 s，表示判断到了哪一位。

我们的思想主要就是逐位移动指针，匹配则移动，不匹配则回溯。

但是，KMP 与朴素算法不同的是，它只会回溯指向 t 的指针 j。

例如，s=\texttt{abcab\color{RED}c\color{BLACK}abx},t=\texttt{abcab\color{RED}x}。红色的是当前指针。

显然，当前位不匹配，那我们如何回溯 j 呢？

我们先来观察一下已经匹配成功的部分，这部分有一个 border，我们可以利用 border 来减少匹配次数。

这是目前的匹配状态：

\texttt{a}	\texttt{b}	\texttt{c}	\texttt{a}	\texttt{b}	\texttt{\color{RED}c}	\texttt{a}	\texttt{b}	\texttt{x}
\texttt{a}	\texttt{b}	\texttt{c}	\texttt{a}	\texttt{b}	\texttt{\color{RED}x}

发现不匹配，我们其实可以如此移动：

\texttt{a}	\texttt{b}	\texttt{c}	\texttt{a}	\texttt{b}	\texttt{\color{RED}c}	\texttt{a}	\texttt{b}	\texttt{x}
\texttt{a}	\texttt{b}	\texttt{\color{RED}c}	\texttt{a}	\texttt{b}	\texttt{x}

其实，这里就是巧妙地运用了 border 的性质，有一部分是已经匹配成功了，那就不需要再次匹配，从而减少匹配次数。

也就是说，回溯时只需使：

j\leftarrow Next(j-1)。

同理，我们可以多次回溯 j，直到匹配成功或为 0。

这样，我们就有效地将时间复杂度降低到 \mathcal{O}(n+m)。

\texttt{Code}

完整代码展示：P3375 【模板】KMP。

注意题目中特殊的下标关系。

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

string s,t;
int n,m;
int Next[1000005];

void get_next(){
    for(int i=1;i<m;i++){ //m 是字符串长度
        int j=Next[i-1]; //初始为最大的 border 长
        while(j>0 && t[i]!=t[j]){ //j!=0 或 不匹配
            j=Next[j-1]; //不断找更小的 j
        }
        if(t[i]==t[j]){ //如果找到，当前答案就是原来答案 +1
            j++;
        }
        Next[i]=j;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>s>>t;
    n=s.length();
    m=t.length();

    get_next();

    int j=0,i=0;
    for(int i=0;i<n;i++){
        while(j>0 && t[j]!=s[i]){ //不匹配，不断回溯 j
            j=Next[j-1];
        }
        if(s[i]==t[j]){ //如果相等，移动 j，匹配下一位
            j++;
        }
        if(j>=m){ //匹配成功
            //输出匹配位置的起始端
            cout<<i-m+2<<"\n"; //题目要求下标从 1 开始
            j=Next[j-1];
        }
    }
    for(int i=0;i<m;i++){
        cout<<Next[i]<<" ";
    }
    return 0;
}

Part 3: Ending

本思路来自于 OI-Wiki。是本人对原思路的分析，自认为更好理解，也是自己去理解的一个过程。

Upd on 2025/1/4：增加了例题。

AC 记录 | 原文链接

\texttt{An Excellent Ending.}