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

算理和算法的關系04-28