schtonn

schtonn

0%

KMP

Posted on Edited on Valine:

前置知识

字符串基础操作。

引入

KMP 是一种字符串匹配算法，意思就是说给出模式串 pat 和文本串 txt（长度各为 m 和 n），找出模式串在文本串中出现的所有位置。

考虑用暴力来解决这一问题，那么：

对于文本串的每一位置，循序匹配模式串，遇到不匹配就退出。此算法时间复杂度 \(O(mn)\)。

KMP算法则用了一 \(O(m)\) 的预处理将时间复杂度缩减到了 \(O(n)\)。

nxt数组

KMP算法预处理了一 nxt 数组，记录模式串的状态转移。利用 nxt 数组，在文本串上的指针可以持续前进，而无需回退，仅需要转移模式串“状态”的位置。

如果我们将一步步的匹配看作状态的转移，那么模式串 pat='ababc' 长这样：

ababc
ababc

当状态转移到 5 时，就匹配成功了。

nxt 数组考虑的是如果在当前位置匹配失败了，模式串的状态应该转移到哪里（文本串上的指针不动，动的是模式串的状态）。

举个例子：

\[aaa\color{green}abab\color{red}a\color{default}bca\] \[\,\color{green}abab\color{red}c\]

当前已经匹配到了状态 4，接下来期待一个 c，但是出现的却是 a，那么模式串状态应该转移到状态 3。

\[aaaab\color{green}aba\color{default}bca\] \[\hspace{2em}\color{green}aba\color{default}bc\]

当然，如果遇到了模式串中都没有的奇奇怪怪的字符，那么自然要转移到状态 0。

处理

如何处理出 nxt 数组呢？

换句话说，我们如何知道应该转移到哪个状态呢？

这里我们就需要考虑模式串截至当前状态的的子串（例如当前状态为 \(i\)，那么考虑 \(pat[0\dots i]\)）的前缀函数。

简单来说，\(s[0\cdots i]\) 的前缀函数就是求一个最大的 \(k(k<i)\)，使得 \(s[0\cdots k]=s[i-k\cdots i]\)，也就是最长的相等前后缀。

在刚才的例子中就是从第四个 b （状态 4）结尾的的后缀和整个模式串的前缀。

这里前缀函数值是2，匹配到的是 ab，所以 nxt[4]=2。

\[\begin{array}{lr}\color{cyan}ab\color{blue}ab\color{default}c\\\rightarrow\rightarrow\end{array}\]

那么新出现的无法匹配的字符就要交给第二个 b 处理。

具体的思路是这样的：

  • 如果新出现的字符在这里能够继续匹配，或者不能继续匹配但是回到了状态 0，那么这里就是它 nxt 数组对应的位置。
  • 否则当前状态同样没能匹配，沿着当前状态的 nxt 继续向前寻找。

比如

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "bits/stdc++.h"
#define MAXN 1000010
using namespace std;
int nxt[MAXN];
int n,m,k;
char txt[MAXN],pat[MAXN];
int main(){
    cin>>pat+1;
    cin>>txt+1;
    n=strlen(txt+1);
    m=strlen(pat+1);
    for(int i=2;i<=m;i++){
        while(k&&pat[i]!=pat[k+1])k=nxt[k];
        if(pat[k+1]==pat[i])k++;
        nxt[i]=k;
    }
    k=0;
    for(int i=1;i<=n;i++){
        while(k>0&&pat[k+1]!=txt[i])k=nxt[k];
        if(pat[k+1]==txt[i])k++;
        if(k==m){cout<<i-m+1<<' ';k=nxt[k];}
    }
    return 0;
}

参考资料

KMP 算法详解

前缀函数与 KMP 算法