原創(chuàng)作品，作者：飛陽。轉(zhuǎn)載請注明出處，謝謝。
http://hi.baidu.com/burtcn

很著名的文本匹配的算法，據(jù)說華為公司的筆試題目曾經(jīng)出過這道
今天終于搞明白了。。別小看這很短的代碼。。

文本匹配的算法還有個(gè)BM算法，據(jù)說是比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;
}