#include
#include
/*
	函數(shù)：int?*MakeSkip（char?*int）
	目的：根據(jù)壞字符規(guī)則做預(yù)處理，建立一張壞字符表
	參數(shù)：
		ptrn?=>?模式串P
		plen?=>?模式串P長(zhǎng)度
	返回：
		int*?-?壞字符表
*/
int?*MakeSkip（char?*ptrnint?plen）
{
	int?i;
	//為建立壞字表，申請(qǐng)256?int空間
	/*一個(gè)字符8位所有字符2的八次方即256*/
	int?*skip?=?（int*）malloc（256*sizeof（int））;
	if（skip?==?NULL）
	{
		printf（“%s““malloc?failed!“）;
		return?0;
	}
	for（i?=?0;?i?	{
		*（skip+i）?=?plen;
	}
	while（plen?!=?0）
	{
		*（skip+（unsigned?char）*ptrn++）?=?plen--;
	}

	//輸出壞字表
	/*	for（i?=?1;?i?		{
			printf（“%d“*（skip+i））;
			printf（“%s“*（skip+i））;
		}
		*/
	return?skip;
}

/*
	函數(shù)：int?*MakeShift（char?*int）
	目的：根據(jù)好后綴規(guī)則做預(yù)處理，建立一張好后綴表
	參數(shù)：
		ptrn?=>?模式串P
		plen?=>?模式串P長(zhǎng)度
	返回：
		int*?-?好后綴表
*/
int?*MakeShift（char?*ptrnint?plen）
{
	int?*shift?=?（int?*）malloc（plen*sizeof（int））;
	int?*sptr?=?shift?+?plen?-?1;//方便給好后綴表賦值的指標(biāo)（指向申請(qǐng)空間最后一個(gè)字符）
	char?*pptr?=?ptrn?+?plen?-1;//記錄邊界位置（指向P最后一個(gè)字符）Search中調(diào)用此表時(shí)，傳入?yún)?shù)為邊界值，所以PPTR用于防止過(guò)多的匹配
	char?c;
	char?*p1?=?ptrn?+?plen?-?2?*p2?*p3;
	if（shift?==?NULL）
	{
		printf（“%s““malloc?failed!“）;
		return?0;
	}
	c?=?*（ptrn?+?plen?-?1）;//保存模式串中最后一個(gè)字符
	*sptr?=?1;//以最后一個(gè)字符為邊界時(shí)，確定移動(dòng)1的距離
	pptr--;//邊界移動(dòng)到倒數(shù)第二個(gè)字符（作者添加的）
	while（sptr--?!=?shift）//該最外層循環(huán)完成給好后綴表中每一個(gè)單位進(jìn)行賦值的工作
	{
	//該do..while循環(huán)完成以當(dāng)前pptr所指的字符為邊界時(shí)，要移動(dòng)的距離
	do{
		while（p1?>=?ptrn?&&?*p1--?!=?c）;//該空循環(huán)，尋找與最后一個(gè)字符C匹配的字符所指向的位置
		p2?=?ptrn?+?plen?-2;
		p3?=?p1;
		while（p3?>=?ptrn?&&?p2?>=?pptr?&&?*p3--?==?*p2--）;//該空循環(huán)，判斷在邊界內(nèi)字符匹配到了什么位置************************執(zhí)行一個(gè)條件，減減一次
	}while（p3?>=?