首页 > 代码库 > KMP小结
KMP小结
next数组表示的是,最长前缀和后缀相等的长度。
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> using namespace std; const int N=1000000; int next[N]; char s[N],t[N]; /*********KMP小结**********/ //求next数组 void getNext(int lt) { int k=-1,i=0; next[0]=-1; while(i<lt) { if(k==-1||s[k]==t[i]) next[++i]=++k; else k=next[k]; } } //KMP求模板串第一次出现的位置 int getIndex(int ls,int lt) { getNext(lt); int i=0,k=0; while(i<ls&&k<lt) { if(k==-1||s[i]==t[k]) { i++; k++; } else k=next[k]; } if(k==lt) return i-lt+1; //返回的下标从0,开始算。 else return -1; } //KMP求模板串出现的次数 int getCnt(int ls,int lt) { getNext(lt); int k=0,cnt=0; for(int i=0;i<ls;i++) { while(k!=-1&&s[i]!=t[k]) k=next[k]; if(s[i]==t[k]) k++; if(k==lt){ cnt++; k=next[k]; } } return cnt; } int main() { cin>>s>>t; int ls=strlen(s); int lt=strlen(t); cout<<getIndex(ls,lt)<<endl; return 0; }
KMP小结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。