首页 > 代码库 > 我的kmp
我的kmp
贴一个我实现的kmp,在这里我的next数组的定义是,上一个前缀和我当前前缀相同的位置应该在哪里,next[0]=-1
ababac的next数组就是-1,-1,0,1,2-1
#include<iostream> using namespace std; int next[10001]; void getnext(char *s){ int i=1,j; next[0]=-1; while(s[i]!=‘\0‘){ j=next[i-1]; while(s[j+1]!=s[i]&&j!=-1) j=next[j]; if(s[j+1]==s[i]) next[i]=j+1; else next[i]=-1; i++; } } void kmp(char*s,char *t)//ÔÚsÖÐÕÒt£»{ getnext(t); int i=0,j=-1,n=strlen(t); while(s[i]!=‘\0‘){ while(t[j+1]!=s[i]&&j!=-1) j=next[j]; if(s[i]==t[j+1]) j++; if(t[j+1]==‘\0‘){ cout<<i-n+1<<endl;j=next[j-1]+1;} i++; } } int main() { char s[20002],t[20002]; while(gets(s)) { gets(t); kmp(s,t); } }
我的kmp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。