KMP算法

2007-05-07 19:12

原创作品，作者：飞阳。转载请注明出处，谢谢。
http://hi.baidu.com/burtcn

很著名的文本匹配的算法，据说华为公司的笔试题目曾经出过这道
今天终于搞明白了。。别小看这很短的代码。。

文本匹配的算法还有个BM算法，据说是比KMP算法还是高效
我感觉下面的代码还算是比较简单易懂的KMP算法。。

#include <stdio.h>
#include <string.h>
void setNext(char pattern[],int next[],int size){          
            int j;
            next[0]=-1;
            for(int i=1;i<size;i++){                    
                      for(j=next[i-1];j>=0&&pattern[i]!=pattern[j+1];j=next[j]);                    
                      next[i]=(j<0&&pattern[i]!=pattern[j+1])?-1:j+1;
            }
}
int match(char source[],char pattern[]){          
            int psize=strlen(pattern);          
            int *next=new int[psize];
            setNext(pattern,next,psize);          
            int i,j;
            int size=strlen(source);
            for(i=0,j=0;i<size;){                    
                      if(source[i]!=pattern[j]){                              
                                if(j>0){                                        
                                          j=next[j-1]+1;
                                }else
                                          i++;
                      }else
                                i++,j++;
                      if(j>=psize) break;
            }          
            return j>=psize?i-psize:-1;
}
int main(){          
            char *source="ababababeababcabdaf";
            char *pattern="ababc";
            printf("%d\n",match(source,pattern));          
            return 0;
}