首页 > 代码库 > BF到KMP,再到后缀数组的字符串匹配
BF到KMP,再到后缀数组的字符串匹配
总结了下,关于BF算法,以及KMP。遇到后缀数组的时候突然发现,KMP还是有用的啊~~~后缀数组更简单,就是代码比较长~~
/* 记住一个公式:KMP算法=BF算法+next数组 ->1.BF算法中,只需要将j=next[j],避免回溯就行了。所以计算 next数组 ->2.计算next数组 做两个变量j,k j=0(用于记录计算P串的位置,j=0~(n-1),最有一个不用计算) k=-1(记录k在P串位置的前后串最长公共前后缀) ******理解下:0~k~(n-1)分k左右一个串,左右串中存在k之前的串与, 后面j(j一般在k~n之间)之前的串相等。然后看next函数里面的递推关系就比较容易理解了 ,简单吧,书上讲解的太蛋碎了~~ adsadjkhasdadabcabdabcabcaaasdasda abcabdabcabcaa 13 */ #include<iostream> using namespace std; const int MAXN=1<<7; char T[MAXN],P[MAXN],next[MAXN];; int N; void input(){ scanf("%s",T); scanf("%s",P); } /* ababdabcd abc */ int BF(){ int n=strlen(T),m=strlen(P); int i=0,j=0; while(i<n){ if(T[i]==P[j]){ i++; j++; }else{ i=i-j+1; j=0;//j=next[j];就是KMP算法了。next数组避免了j=0的回溯!!!!!!! } if(j==m) return i-j; } return -1; } /* 由BF改进过来的KMP */ int KMP(){ int n=strlen(T),m=strlen(P); int i=0,j=0; while(i<n){ if(T[i]==P[j]){ i++; j++; }else{ i=i-j+1; j=next[j]; } if(j==m) return i-j; } return -1; } int getNext(){ int n=strlen(P); next[0]=-1; int j=0,k=-1; while(j<(n-1)){ if(k==-1 || P[j]==P[k]){ j++; k++; next[j]=k; /* //将next[j]=k;替换成下面的代码,避免了next中k的回溯 if(P[j]!=P[k]){ next[j]=k; }else next[j]=next[k]; */ }else{ k=next[k]; } } return *next; //其实可以返回void类型的,但是就是想测试下如何返回数组来着。这个多余了。 } int main(){ input(); printf("BF:%d\n",BF()); getNext(); int i=0,n=strlen(P); while(i<n) printf("%d ",next[i++]); printf("\n"); printf("KMP:%d\n",KMP()); return 0; }
KMP瞬间简单了吧~~~~看书会死人的~~
BF到KMP,再到后缀数组的字符串匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。