KMP模式匹配算法

Question

请给我一段完整的KMP模式匹配算法的C语言代码，书上面的我看不懂啊，最好可以把头文件之类的也发来

Answer 1

这里有个相似的问题，也是我回答的，讲了原理
http://zhidao.baidu.com/question/329386416.html
如果你只要代码的话
一个简单的代码
#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);

char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;

int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}

int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}

void get_next(char *t,int *next)
{

int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}

}

Answer 2

//模式匹配,kmp算法,复杂度O(m+n)
//返回匹配位置,-1表示匹配失败,传入匹配串和模式串和长度
//可更改元素类型,更换匹配函数
#define MAXN 10000
#define _match(a,b) ((a)==(b))
typedef char elem_t;

int pat_match(int ls,elem_t* str,int lp,elem_t* pat){
int fail[MAXN]={-1},i=0,j;
for (j=1;j<lp;j++){
for (i=fail[j-1];i>=0&&!_match(pat[i+1],pat[j]);i=fail[i]);
fail[j]=(_match(pat[i+1],pat[j])?i+1:-1);
}
for (i=j=0;i<ls&&j<lp;i++)
if (_match(str[i],pat[j]))
j++;
else if (j)
j=fail[j-1]+1,i--;
return j==lp?(i-lp):-1;
}

Answer 3

发过去你还是看不懂追问

那要怎么做呢？

追答

首先要理解这个算法，它是干什么用的，怎么用的，过程是什么，先要有个大概，不要具体的。这些都理解以后才能一步一步分析。