神马文学网KMP算法_飞花如梦，阳光灿烂的日子
来源：百度文库 编辑：神马文学网 时间：2024/04/29 19:15:33
原创作品，作者：飞阳。转载请注明出处，谢谢。
http://hi.baidu.com/burtcn
很著名的文本匹配的算法，据说华为公司的笔试题目曾经出过这道
今天终于搞明白了。。别小看这很短的代码。。
文本匹配的算法还有个BM算法，据说是比KMP算法还是高效
我感觉下面的代码还算是比较简单易懂的KMP算法。。
#include
#include
void setNext(char pattern[],int next[],int size){
int j;
next[0]=-1;
for(int i=1;i
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
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;
}