字符串匹配算法详解 BM算法 c语言实现

#include
#include
/*
	函数：int *MakeSkip（char *int）
	目的：根据坏字符规则做预处理，建立一张坏字符表
	参数：
		ptrn => 模式串P
		plen => 模式串P长度
	返回：
		int* - 坏字符表
*/
int *MakeSkip（char *ptrnint plen）
{
	int i;
	//为建立坏字表，申请256 int空间
	/*一个字符8位所有字符2的八次方即256*/
	int *skip = （int*）malloc（256*sizeof（int））;
	if（skip == NULL）
	{
		printf（“%s““malloc failed!“）;
		return 0;
	}
	for（i = 0; i < 256; i++ ）
	{
		*（skip+i） = plen;
	}
	while（plen != 0）
	{
		*（skip+（unsigned char）*ptrn++） = plen--;
	}

	//输出坏字表
	/*	for（i = 1; i < 256; i++ ）
		{
			printf（“%d“*（skip+i））;
			printf（“%s“*（skip+i））;
		}
		*/
	return skip;
}

/*
	函数：int *MakeShift（char *int）
	目的：根据好后缀规则做预处理，建立一张好后缀表
	参数：
		ptrn => 模式串P
		plen => 模式串P长度
	返回：
		int* - 好后缀表
*/
int *MakeShift（char *ptrnint plen）
{
	int *shift = （int *）malloc（plen*sizeof（int））;
	int *sptr = shift + plen - 1;//方便给好后缀表赋值的指标（指向申请空间最后一个字符）
	char *pptr = ptrn + plen -1;//记录边界位置（指向P最后一个字符）Search中调用此表时，传入参数为边界值，所以PPTR用于防止过多的匹配
	char c;
	char *p1 = ptrn + plen - 2 *p2 *p3;
	if（shift == NULL）
	{
		printf（“%s““malloc failed!“）;
		return 0;
	}
	c = *（ptrn + plen - 1）;//保存模式串中最后一个字符
	*sptr = 1;//以最后一个字符为边界时，确定移动1的距离
	pptr--;//边界移动到倒数第二个字符（作者添加的）
	while（sptr-- != shift）//该最外层循环完成给好后缀表中每一个单位进行赋值的工作
	{
	//该do..while循环完成以当前pptr所指的字符为边界时，要移动的距离
	do{
		while（p1 >= ptrn && *p1-- != c）;//该空循环，寻找与最后一个字符C匹配的字符所指向的位置
		p2 = ptrn + plen -2;
		p3 = p1;
		while（p3 >= ptrn && p2 >= pptr && *p3-- == *p2--）;//该空循环，判断在边界内字符匹配到了什么位置************************执行一个条件，减减一次
	}while（p3 >=