KMP
程序员文章站
2022-04-17 21:51:18
KMP $KMP$ 算法是一种改进的字符串匹配算法,由 $D.E.Knuth$ , $J.H.Morris$ 和 $V.R.Pratt$ 提出的,简称 $KMP$ 算法。 基本原理 $KMP$ 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 ......
kmp
\(kmp\) 算法是一种改进的字符串匹配算法,由 \(d.e.knuth\) , \(j.h.morris\) 和 \(v.r.pratt\) 提出的,简称 \(kmp\) 算法。
基本原理
\(kmp\) 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 \(next\) 数组实现,数组本身包含了模式串的局部匹配信息。
首先对模式串进行自身匹配,得到 \(next\) 数组。 \(next[i]\) 为满足 \(s_2[i-z,...,i-1]=s_2[0,...,z-1]\) 的最大 \(z\) 值,即 \(s_2\) 的子串 \(s_2[0,...,i]\) 最长公共前后缀的长度。
这样在进行模式串与文本串的匹配时(假设当前为文本串的 \(s_1[i]\) 与模式串的 \(s_2[j]\) 进行匹配),一旦发生失配情况,可以只移动模式串而不回溯指针。移动时,只需要将 \(s_2[0,...,j-1]\) 前缀移动到后缀的位置,然后,从模式串子串 \(s_2[0,...,j-1]\) 前缀的下一位即 \(next[j]\) 开始与文本串当前位 \(i\) 进行匹配。
效率分析
一般情况下, \(kmp\) 算法的期望时间复杂度为 \(o(n+m)\) ,其中 \(n,m\) 分别是文本串 \(s_1\) 和模式串 \(s_2\) 的长度。
核心代码
ll len1,len2,next[maxn],pos[maxn],ans; string s1,s2; void pre() { len2=s2.length(); ll j=0; next[0]=0; for(ll i=1;i<len2;i++) { while(j&&s2[i]!=s2[j])j=next[j]; if(s2[i]==s2[j])j++; next[i+1]=j; } } void kmp() { len1=s1.length(); pre(); ll j=0; for(ll i=0;i<len1;i++) { while(j&&s1[i]!=s2[j])j=next[j]; if(s1[i]==s2[j])j++; if(j==len2) { pos[++ans]=i-j+2; j=next[j]; } } return; }
例题解析
洛谷 p3375 【模板】kmp字符串匹配
给出一个文本串 \(s_1\) 和一个模式串 \(s_2\) ,求 \(s_2\) 在 \(s_1\) 中出现的所有位置并输出前缀数组。
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define maxn 1000005 #define maxm 200005 #define inf 1234567890 #define p 1000000007 template<class t>inline bool reads(t &x) { register char c=getchar(); while(c==' '||c=='\n'||c=='\r'||c=='\t')c=getchar(); if(c==eof)return false; while(c!=' '&&c!='\n'&&c!='\r'&&c!='\t')x+=c,c=getchar(); return true; } template<class t>inline void print(t x) { if(x<0)putchar('-'),x=-x; if(x>9)print(x/10); putchar('0'+x%10); } template<class t>inline void print(t x,char c){print(x),putchar(c);} ll len1,len2,next[maxn],pos[maxn],ans; string s1,s2; void pre() { len2=s2.length(); ll j=0; next[0]=0; for(ll i=1;i<len2;i++) { while(j&&s2[i]!=s2[j])j=next[j]; if(s2[i]==s2[j])j++; next[i+1]=j; } } void kmp() { len1=s1.length(); pre(); ll j=0; for(ll i=0;i<len1;i++) { while(j&&s1[i]!=s2[j])j=next[j]; if(s1[i]==s2[j])j++; if(j==len2) { pos[++ans]=i-j+2; j=next[j]; } } return; } int main() { reads(s1),reads(s2); kmp(); for(ll i=1;i<=ans;i++)print(pos[i],'\n'); for(ll i=1;i<=len2;i++)print(next[i],' '); return 0; }