首页 > 代码库 > KMP模板
KMP模板
KMP算法是快速字符串匹配算法,朴素的暴力算法的时间复杂度为O(n*m),而KMP通过对模式串进行相应的处理,能够达到O(m+n)的速度。
我们知道在字符串匹配的时候最消耗时间的就是当匹配到第 i 个位置发现不匹配时,下一次又对模式串进行一次重新匹配,那么假如模式串中有很多相同的字母的话,这样做了很多重复的事情,那么我可以对模式串进行一定的处理,处理处一个对应的数组,让他保存假如这里不匹配是我下次应该从哪儿重新开始。
每次当前的一个值是根据前面是否匹配的到。
这是预处理函数:
void getfill(string s) { memset(f,0,sizeof(f)); //根据其前一个字母得到 for(int i=1;i<s.size();i++) { int j=f[i]; while(j && s[i]!=s[j]) j=f[j]; f[i+1]=(s[i]==s[j])?j+1:0; } }
然后匹配函数就很好写了、
int find(string a,string s) { getfill(s);int j=0; for(int i=0;i<a.size();i++) { while(j && a[i]!=s[j]) j=f[j]; if(a[i]==s[j]) j++; if(j==s.size()){ return i-s.size()+1; } } }
poj3461 ,求一个模式串在字符串中的出现次数。
#include<cstdio> #include<cstring> #include<algorithm> #include <iostream> #include <string> using namespace std; int f[ 15000]; void getfill(string s) { memset(f,0,sizeof(f)); //根据其前一个字母得到 for(int i=1;i<s.size();i++) { int j=f[i]; while(j && s[i]!=s[j]) j=f[j]; f[i+1]=(s[i]==s[j])?j+1:0; } } int find(string a,string s) { int ans=0; getfill(s);int j=0; for(int i=0;i<a.size();i++) { while(j && a[i]!=s[j]) j=f[j]; if(a[i]==s[j]) j++; if(j==s.size()){ ans++; } } return ans; } int main() { string s,a; int T; scanf("%d",&T); while(T--) { getchar(); cin>>s>>a; int ans=find(a,s); printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。