- 相关推荐
KPM算法心得体会
next函数求法（目前只能死记） 0 1 2 3 4 a b a b c next -1 0 0 1 2 过程： 第0位，next[0]=-1 第1位，next[1]=0 第2位，b!=p[0]=a => next[2]=next[next[1]]=-1+1=0 第3位，a==p[0]=a => next[3]=0+1=1 第4位，b==p[1]=b => next[3]=1+1=2 技巧：算哪位就看前一位 -------------------------------------------- next优化过程 0 1 2 3 4 a b a b c next -1 0 0 1 2 next_adv -1 0 -1 0 2 第1位，b!=p[0]=a => next_adv[1]=next[1]=0，不变 第2位，a==p[0]=a => next_adv[2]=next[0]=-1 第3位，b==p[1]=b => next_adv[3]=next[1]=0 第4位，c!=p[2]=a => next_adv[1]=next[1]=2，不变 技巧：比较p[i]和p[next[i]]，不一样，不变，一样，赋值 ---------------------------------------------- KPM匹配过程 aaaaabababcaaa ab ab ab ab ababc ababc 产生匹配 ab ab --------------------------------------------- 源代码如下： #include <iostream> #include <cstring> using namespace std; void getNext(const char *p,int next[])//多算一位的next算法 { int j=-1,i=0; next[0]=-1; int len=strlen(p); while(i<=len) { if(j==-1||p[i]==p[j]) { i++; j++; //next[i]=j;//以下是改进的算法 if(p[i]!=p[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; } } //返回匹配的首位置 int kpm_search( char *t,char *p,int next[]) { int j=0,i=0; int len_t=strlen(t); int len_p=strlen(p); while(i<len_t) { if(j==-1||t[i]==p[j]) { i++; j++; } else j=next[j]; } if(j>=len_p) { //j=0;重置j可以继续下一个查找 return i-len_p; } return -1; } int main() { char p[]=ababc; char t[]=aaaaabababcaaa; int len=strlen(p); int next[len+1]; get_nextval(p,next); for(int i=0; i<len; i++) cout<<next[i]<<,; cout<<endl; cout<<kmp_match(t,p,next,0)<<endl; return 0; }【KPM算法心得体会】相关文章：
数学算法04-28
算法岗位职责03-15
手指快算法简介04-28
算理和算法04-28
乘法的简便算法教案04-28
算理与算法的有效结合04-28
算法优化要五问04-28
算法初步的教学策略04-28
算理和算法的关系04-28