KMP算法C语言程序

最简洁的KMP算法

#include <stdio.h>

#include <stdlib.h>
#include <string.h>

#define ERROR 0
#define TRUE 1;

int InitData(char **source,char **target,int **value)
{
char ch;
int i=0;
(*source)=(char*)malloc(sizeof(char)*100);
(*target)=(char*)malloc(sizeof(char)*100);
(*value)=(int*)malloc(sizeof(int)*100);

if(!(*source)||!(*target)||!(*value))
return ERROR;

printf("请输入源字符串，以#结束：\n");

while((ch=getchar())!='#')
{
(*source)[i ]=ch;
(*source)[i]='\0';

}

getchar(); //抵消缓冲

i=0; //重置

printf("请输入要匹配的字符串，以#结束：\n");

while((ch=getchar())!='#')
{
(*target)[i ]=ch;
(*target)[i]='\0';

}

//初始化Value数组
for(i=0;i<100;i )
{
(*value)[i]=0;

}

return TRUE;

}
//得出target中的匹配值
int GetValue(char *target,int *value)
{
char *head,*tail;
int temp;
//ABCDABD
//ABCDAB


int i=1,j=0;

head=(char*)malloc(sizeof(char)*100);
tail=(char*)malloc(sizeof(char)*100);
if(!head||!tail)
return ERROR;

for(i=1;i<strlen(target);i )//从头到尾
{
j=0;
while(target[j]!='\0')//复制到临时数组
{
head[j]=target[j];
tail[j]=target[j];

j ;

head[j]='\0';
tail[j]='\0';

}
head[i]='\0';
tail[i 1]='\0';

for(j=0;j<i;j )
{
if(strcmp(head,tail 1 j)==0)//比较
{
value[i]=strlen(head);
break;
}
temp=strlen(head)-1;
head[temp]='\0';

}

}

}
//KMP处理方法
int KMP(char *source,char *target,int *value)
{
int i=0,j=0,x,y;

while(i<strlen(source)) //不回溯，source走到尾
{
if(source[i]==target[j]&&j<strlen(target))
{
i ;
j ;
}
else if(j>=strlen(target))
{
printf("相等字符串的位置为%d\n",i-strlen(target));
printf("%s\n",source);
for(x=0;x<i-strlen(target);x )
{
printf(" ");
}
printf("%s\n",target);

return TRUE;

}

else if(source[i]!=target[j])
{
if(j==0)
{
j=0;
i ;
}

else
{
j=value[j-1];
}

}


}
if(i>=strlen(source)&&j>=strlen(target))
{
printf("相等字符串的位置为%d\n",i-strlen(target));
printf("%s\n",source);
for(y=0;y<i-strlen(target);y )
{
printf(" ");
}
printf("%s\n",target);
}
else
printf("未找到...");


}


int main()
{
char *source,*target; //source源字符串，target要匹配的字符串
int *value; //存放匹配值
int i=0;

InitData(&source,&target,&value); //初始化字符串

GetValue(target,value);

KMP(source,target,value);


}