点击刷新
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+5), M(1e6+5); 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[0]=0; for(int i=ls=1; s[i]; i++, ls++){ for(;k&&s[k]!=s[i];) k=nt[k]; nt[i]=s[i]==s[k]?++k:k; } ans=k=0; for(int i=0; t[i]; i++){ //k:t[0..i-1]的匹配长度 for(;k&&s[k]!=t[i];) k=nt[k-1]; //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+10; char s[MAX_N], t[MAX_N]; int nt[MAX_N]; void get_next(char *s){ nt[0]=-1; int k=-1; for(int i=1; s[i]; i++){ while(k!=-1&&s[k+1]!=s[i]) k=nt[k]; if(s[k+1]==s[i]) k++; nt[i]=k; } } int ans; void match(char *s, char *t){ int ls=strlen(s), k=-1; for(int i=0; t[i]; i++){ while(k!=-1&&s[k+1]!=t[i]) k=nt[k]; if(s[k+1]==t[i]) k++; if(k==ls-1) ans++; } } int main(){ int N; scanf("%d", &N); while(N--){ scanf("%s%s", s, t); get_next(s); ans=0; match(s, t); printf("%d\n", ans); } return 0; }
© 著作权归作者所有
相关热门文章
发表评论
