KMP算法——深入骨髓的领悟
2022/8/24 14:23:17
本文主要是介绍KMP算法——深入骨髓的领悟,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前缀函数与KMP算法
真前缀: S中不全等于S的前缀
前缀函数定义
\(s[0\dots i]\) 的真前缀与真后缀相等的最大长度为 \(\pi(i)\) 。
规定 \(\pi(0)=0\) 。
计算前缀函数
1.朴素算法
按照定义 , 按 \(i=1\dots n-1\) 计算 \(\pi(i)\) 。
令长度 \(j\) 从最大前缀长度 \(i\) 开始一直到 \(0\) 。
用 \(substr()\) 截取 \(s[0\dots j-1]\) 和 \(s[i-j+1,i]\)
若相等,则 \(\pi(i) =j\) ,否则 \(j--\) ,直到 \(j<0\) 时,\(\pi(i)=0\) 。
代码
vector<int> prefix_function(string s) { int n = s.length(); vector<int> pi(n); for(int i=1;i<n;++i) { for(int j=i;~j;--j) { if(s.substr(0,j) == s.substr(i-j+1,j)) { pi[i] = j; break; } } } return pi; }
2.优化一
\(\pi(i+1) <= \pi(i)+1\) ;
因为相当于在 \(s[0-i]\) 后加了一个 \(s[i+1]\) ,最大后缀最多增加 \(1\)
所以 相对于前一段代码 \(j = i\dots 0\) ,优化为 \(j=\pi(i-1)+1\dots 0\) 。
代码:
vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 1; i < n; i++) for (int j = pi[i - 1] + 1; j >= 0; j--) // improved: j=i => j=pi[i-1]+1 if (s.substr(0, j) == s.substr(i - j + 1, j)) { pi[i] = j; break; } return pi; }
3.优化二
第一个优化中,我们考虑了 \(\pi(i+1)=\pi(i)+1\) 的最优情况,那么当最优情况不成立时,跳转到一个次优情况。
我们找到仅次于 \(\pi(i)\) 的第二长度 \(j\) ,使\(s[0\dots j-1]=s[i-j+1\dots i]\) 。
显然 \(j\) 是此时的最好选择。
这时若 \(s[j]=s[i+1]\) ,那么 \(\pi(i+1)=j+1\) 。
如下图:
可以看出,\(j\) 等价于 \(s[0\dots \pi(i)-1]\) 的前缀函数,即\(j=\pi(\pi(i-1))\) ;同理 ,次于 \(j\) 的第二长度 \(j^{(2)}=\pi(j-1)\) 。
得到关于 \(j\) 的状态转移方程:
\(j^{(n)} = \pi(j^{(n-1)}-1)\) , \(j^{(n-1)}>0\) 。
终极算法:
vector<int> prefix_function(string s) { int n = s.length(); vector<int> pi(n); for(int i = 1; i < n ; i++) { int j = pi[i-1]; while(j>0 && s[i]!=s[j]) j = pi[j-1]; if(s[i]==s[j]) ++j;//找到了满足条件的 j,j++后从i-1转移到 i pi[i] = j; } return pi; }
前缀函数应用:KMP算法
对于一个文本 \(s_1\) 和一个匹配串 \(s_2\) ,求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。
解法:
将 \(s_2\) 和 \(s_1\) 放在一个串 \(s\) 里, 用分隔符隔开。设 \(s_2\) 长度为 \(n\) 。
对 \(s\) 求前缀函数,由于分隔符(位置在 \(n\) )的存在, \(n\) 以后的所有\(\pi(i)\) 都不可能超过 \(n\) ,当 \(\pi(i)==n\) 时,意味着最长前缀等于最长后缀,且最长前缀长度为 \(n\) ,这个最长前缀就是 \(s_2\) 。
那么 \(s_2\) 在 \(s_1\) 中的位置就是 \(i-2\times \pi(i)\) ,下标 \(0\) 开始。
洛谷P3375 【模板】KMP字符串匹配
代码:
#include<iostream> #include<string> #include<vector> #include<cstdio> using namespace std; const int maxn = 1e6+7; string s1,s2; void prefix_function(string s,vector<int>& pi) // pi直接传进函数里 { int n = (int)s.length(); for(int i = 1; i < n; ++i) { int j = pi[i-1]; while(j>0 && s[i]!=s[j]) j = pi[j-1]; if(s[i]==s[j]) ++j; pi[i] = j; // 若 j = 0 ,则说明 s[i] != s[j] } return ; } int main() { freopen("data.in","r",stdin); string s; cin>>s1>>s2; s = s2 + '$' + s1; // 分隔符隔开 //cout<<s<<endl; int lens2 = (int)s2.length(); int n = (int)s.length(); //cout<<lens2<<" "<<n<<endl; vector<int> pi(n); prefix_function(s,pi); for(int i=lens2+1;i<=n;++i) // 下标0 { if(pi[i] == lens2) { printf("%d\n",i-2*lens2+1); } } pi.clear(); prefix_function(s2,pi); for(int i=0;i<lens2;++i) { cout<<pi[i]<<" "; } return 0; }
\(end\)
.......了吗?
被巨佬拜访后,我重审了KMP,发现 OI-Wiki 上的做法不是 KMP 的理解方式,只是对前缀函数的naive使用。
实际上 KMP 算法的流程:
- 对模式串求 pi,计入pi数组;
- 拿模式串和文本串匹配 长度 \(j\) ;
这两个过程本质都是求前缀函数,只是一个是自己匹配自己,另一个是自己匹配别人。
同时,在 KMP 算法里,\(\pi\) 数组被称为 失配数组,正如它的名字,当匹配不成立时,失配数组中的值就是当前次优状态,通过失配数组跳至这个次优状态。
代码:
#include<iostream> #include<string> #include<vector> #include<cstdio> using namespace std; const int maxn = 1e6+7; int ls,lt; void prefix_function(string s,vector<int>& pi) // pi直接传进函数里 { int n = (int)s.length(); for(int i = 1; i < n; ++i) { int j = pi[i-1]; while(j>0 && s[i]!=s[j]) j = pi[j-1]; if(s[i]==s[j]) ++j; pi[i] = j; // 若 j = 0 ,则说明 s[i] != s[j] } return ; } string s,t; void match(vector<int>& pi)//模式串匹配文本串 { int j=0; for(int i=0;i<ls;++i) { for(;j&&s[i]!=t[j];j=pi[j-1]); if(s[i]==t[j]) ++j; if(j==lt) printf("%d\n",i-lt+2); } } int main() {ios::sync_with_stdio(0); cin>>s>>t; ls = (int)s.length(); lt = (int)t.length(); vector<int> pi(lt); prefix_function(t,pi); match(pi); for(int i=0;i<lt;++i) printf("%d ",pi[i]); return 0; }
为了与国际接轨,我从 2022/07/13 开始做出以下规定:
- 字符串下标 0 开始;
- \(pi[i]\) 表示长度为 \(i\) 的前缀的失陪长度;
这样,KMP的模板就变成了:
void get_KMP(string s) { int n = (int)s.length(); int j = 0; //请注意,j是当前匹配长度 pi[0] = 0; for(int i=1;i<n;++i) { while(j&&s[i]!=s[j]) j = pi[j];// j+=(s[j]==s[i]); pi[i+1] = j; // i 是下标,i+1 是长度 } }
神题:P2375 [NOI2014] 动物园
这题让求每个前缀的不重叠KMP个数。
即 \(最长前后缀 \le len/2\) ;
那么从 下标 \(0\dots n-1\) 重新依次匹配,原来求得的 \(pi\) 不能再用;
因为原先的 \(pi\) 可能包含重叠区域 ,而我们要的最长前后缀不能有重叠;
所以根据KMP的思想,用现在的合法最长前后缀推下一个;
题目要求每个前缀的所有不重叠匹配串,
假如 \(j\) 长度合法 , 那么下一个合法的就是 \(pi[j]\) , 下下个就是 \(pi[pi[j]]\) \(\dots\) 一直到 \(0\) (0不计数)
\(num\) 数组实际上是当前的 \(j\) 能跳失配指针几次到 0 ;
而板子中 \(pi[i+1]=j\) ,正是把 \(i+1\) 的失配指针作为 \(j\) 。
所以 \(num\) 的递推方式是: num[i+1]=num[j]+1;
此题就完结了;
代码:
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6+3; const int mod = 1e9+7; int pi[maxn],num[maxn],pre[maxn]; void get_KMP(string s) { int j=0; pi[0]=0; pre[0] = 0, pre[1] = 1; int n = (int)s.length(); for(int i=1;i<n;++i) { while(j && s[i]!=s[j]) j = pi[j]; if(s[i]==s[j]) ++j; pi[i+1] = j; pre[i+1] = pre[j] + 1; //递推 } } signed main() {ios::sync_with_stdio(0); int T; cin>>T; for(;T--;) { string s; cin>>s; int n = s.length(); memset(pi,0,sizeof(pi)); memset(pre,0,sizeof(pre)); memset(num,0,sizeof(num)); get_KMP(s); int ans = 1; int j=0; for(int i=1;i<n;++i) { while(j && s[i]!=s[j]) j = pi[j]; if(s[i]==s[j]) ++j; while(j+j > (i+1)) j=pi[j]; ans = (ans * (pre[j]+1) %mod); } cout<<ans<<'\n'; } return 0; }
这篇关于KMP算法——深入骨髓的领悟的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-15JavaMailSender是什么,怎么使用?-icode9专业技术文章分享
- 2024-11-15JWT 用户校验学习:从入门到实践
- 2024-11-15Nest学习:新手入门全面指南
- 2024-11-15RestfulAPI学习:新手入门指南
- 2024-11-15Server Component学习:入门教程与实践指南
- 2024-11-15动态路由入门:新手必读指南
- 2024-11-15JWT 用户校验入门:轻松掌握JWT认证基础
- 2024-11-15Nest后端开发入门指南
- 2024-11-15Nest后端开发入门教程
- 2024-11-15RestfulAPI入门:新手快速上手指南