KMP 算法总结

KMP算法是基本的字符串匹配算法，但是代码实现上有一些细节容易错。这篇随笔将认真总结一下。

KMP算法的核心是：

The KMP algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. (form Wikipedia)

首先定义几个概念

对于长为$L$的字符串$s[0..L-1]$, 我们定义$s$的一个前缀 (prefix) 为字符串$s[0..i], 0\le i<L$, 记作$s_i$; $s$的一个正规前缀 (proper prefix) 为$s[0..i], 0\le i<L-1$；另外空串是任意串 (包括空串) 的正规前缀. 若$s$的某个正规前缀 $s[0..i] (i<L-1)$ 恰是$s$的后缀，则将此前缀称作$s$的一个关键前缀 (critical prefix)。

另外我们定义: 空串是任意串 (包括空串) 的关键前缀。

对于模式串$w$, 预处理一个长为$|w|$的数组$next[0..|w|-1]$，$next[i]$表示$w$的前缀$w_i$的最长关键前缀的长度。

借助$next[]$数组,可以在$O(|s|)$时间内完成匹配。

具体实现以及复杂度分析略过，留下K. M. P. 三人论文的链接

Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323–350.doi:10.1137/0206024.

下面详细介绍一下next数组的求法. 显然我们有

\[next[i]=\begin{cases} 0, \text{if $i=0$; } \\ 1+\max\{i \mid next[i], &\text{if $s[next[i-1]]=s[i]$;} \\ \end{cases}\]

题目链接：hihocoder 1015

#include <bits/stdc++.h>

using namespace std;

const int N(1e4+), M(1e6+);

char s[N], t[M];

int nt[N];

int main(){

    int n;

    scanf("%d", &n);

    for(int ls, k, ans;n--;){

        scanf("%s%s", s, t);

        k=nt[]=;

        for(int i=ls=; s[i]; i++, ls++){

            for(;k&&s[k]!=s[i];) k=nt[k];

            nt[i]=s[i]==s[k]?++k:k;

        }

        ans=k=;

        for(int i=; t[i]; i++){

            //k:t[0..i-1]的匹配长度

            for(;k&&s[k]!=t[i];) k=nt[k-];     //error-prone

            if(t[i]==s[k]){

                k++;

                if(k==ls) ans++;

            }

        }

        printf("%d\n", ans);

    }

}

代码中注释的两处是容易写错的地方，典型错误是

for(;k&&s[k]!=s[i];) k=nt[k];

for(;k&&s[k]!=t[i];) k=nt[k];

这个错误坑在：往往可过样例，提交后不会WA而是会TLE。

还可以将next[i]定义成前缀w[0..i]的最长关键前缀的长度减一，这时可将next[i]的含义表述为前缀w[0..i]的最长关键前缀的结束位置。

代码只消稍作变动

#include<bits/stdc++.h>

using namespace std;

const int MAX_N=1e6+;

char s[MAX_N], t[MAX_N];

int nt[MAX_N];

void get_next(char *s){

    nt[]=-;

    int k=-;

    for(int i=; s[i]; i++){

        while(k!=-&&s[k+]!=s[i]) k=nt[k];

        if(s[k+]==s[i]) k++;

        nt[i]=k;

    }

}

int ans;

void match(char *s, char *t){

    int ls=strlen(s), k=-;

    for(int i=; t[i]; i++){

        while(k!=-&&s[k+]!=t[i]) k=nt[k];

        if(s[k+]==t[i]) k++;

        if(k==ls-) ans++;

    }

}

int main(){

    int N;

    scanf("%d", &N);

    while(N--){

        scanf("%s%s", s, t);

        get_next(s);

        ans=;

        match(s, t);

        printf("%d\n", ans);

    }

    return ;

}

巴特西

KMP 算法总结

最新文章

热门文章