小桥流水的博客

/***************************************************
*	Original Filename: 		wm.h
*	Created/Modified: 		Andy_guo								
*	Date:					2009/11/22			
*	Main Purpose:			WM算法
*	Comments:	
****************************************************/
#pragma once
 
//哈希表大小
#define HASHTABLESIZE (256*256)
//哈希表类型
#define HASH_TYPE short
//移动表大小
#define SHIFTTABLESIZE (256*256)
//模式串的最大长度MAXN - 1
#define MAXPATTERN 10001	
//单词最大长度为MAXM - 1
#define WORDMAX 51	
 
#include "winsock2.h"
#include "atlstr.h"
 
//=================================//
//模式结构体
//=================================//
typedef struct WMPATTERNSTRUCT
{
	char*				psPat;	//模式内容
	unsigned			psLen;	//模式的长度
	WMPATTERNSTRUCT*	next;	//下一个模式指针
}WMPATTERNSTRUCT;
 
//=================================//
//已经匹配模式结构体
//=================================//
typedef struct matchedPattern
{
	char	matchedPtn[20];	//模式内容
	int		matchedSum;		//模式的长度
 
}MATCHEDPATTERN;
 
//=================================//
//wm综合结构体
//=================================//
typedef struct WMSTRUCT
{
	WMPATTERNSTRUCT*	plist;				//模式指针链表
	WMPATTERNSTRUCT*	msPatArray;			//模式数组,用来存放模式内容
	unsigned short*		msNumArray;			//模式数组中有相同哈希值的个数
	int					msNumPatterns;		//模式数量
	unsigned			msNumHashEntries;	//哈希表条目的数量
	HASH_TYPE*			msHash;				//last 2 characters pattern hash table
	unsigned char*		msShift;			//bad word shift table
	HASH_TYPE*			msPrefix;			//first 2 characters prefix table
	int					msSmallest;			//模式的最小长度
}WMSTRUCT;
 
/****************************************************/
class CWM
{
public:
	CWM(void);
 
	~CWM(void);
 
	//WM综合结构体
	WMSTRUCT* m_pWmStruct;
 
	//已经匹配模式结构体
	MATCHEDPATTERN* m_pMatchedPtn;
 
	//获取指定文件名路径
	/*void GetFilePath(const char* strFileName, char* strFilePath);*/
 
	/**	
	*	建立shift移动表
	*	@pWmStruct		WM结构体指针
	*	@return void
	**/
	void CreateShiftTable(WMSTRUCT* pWmStruct);
 
	/**	
	*	建立prefix前缀表
	*	@pWmStruct		WM结构体指针
	*	@return void
	**/
	void CreatePrefixTable(WMSTRUCT* pWmStruct);
 
	/**	
	*	Hash哈希表的建立
	*	@pWmStruct		WM结构体指针
	*	@return int
	**/
	int CreateHashTable(WMSTRUCT* pWmStruct);
 
	/**	
	*	从配置文件中加载关键词
	*	@pWmStruct		WM结构体指针
	*	@return int
	**/
	int LoadPatternToArray(WMSTRUCT* pWmStruct);
 
	/**	
	*	字符串哈希值从小到大排列
	*	@pWmStruct		WM结构体指针
	*	@return void
	**/
	void Sort(WMSTRUCT* pWmStruct);
 
	/**
	*	WM算法模式匹配
	*	@pchSrcText		要过滤的文本内容
	*	@nTextLen		原文本内容长度
	*	@pList			返回匹配的链表指针
	*	@return	int
	**/
	int WMPatternMatch(unsigned char* pchSrcText, int nTextLen, WMPATTERNSTRUCT** pList);
 
	/**
	*	后缀哈希值相同，比较前缀以及整个字符匹配
	*	@nIndex			散列值
	*	@pchDestText	文本内容
	*	@windowBgn	    匹配模式窗口头
	*	@return	int
	**/
	int WMPrefixMatch(int nIndex, unsigned char* pchDestText, unsigned char* T,WMPATTERNSTRUCT**);
 
	/**
	*	用指定的字符串替换文本中出现的要替换的字符串
	*	@pchInput	 	含特殊字符的字符串
	*	@pchOutput		转换后的字符串
	*	@pSrc			要转换的特殊字符	
	*	@pDst			要转换的目的字符
	*	@return	char*	转换后的字符串指针
	**/
	char* Substitute(char* pInput, char* pOutput, char* pSrc, char* pDst);
 
	/*************************内联、静态函数***************************/
 
	/**
	*	哈希映射函数
	*	@T			哈希函数键值
	*	@return		unsigned short
	**/
	static unsigned short HASH16(unsigned char* T)
	{
		//每个字节放一位字符,前一个字符左移8位与后面的字符
		return (unsigned short) ((*T) << 4 | *(T + 2));
	}
 
	/**
	*	判断是否是单字符
	*	@chChar
	*	@return	bool
	**/
	inline bool IsSingleChar(char chChar)
	{
		return chChar > 0;
	}
 
	/**
	*	判断是否是有效的单字符
	*	@chChar
	*	@return	bool
	**/
	inline bool IsValidSingleChar(char chChar)
	{
		return (chChar >= '0' && chChar <= '9')
			|| (chChar >= 'A' && chChar <= 'Z')
			|| (chChar >= 'a' && chChar <= 'z')
			|| (chChar == ' ');
	}
 
	/**	
	*	判断是否是有效的双字符(中文)
	*	0xA3B0-0xA3B9，全角数字
	*	0xA3C1-0xA3DA，全角大写字母
	*	0xA3E1-0xA3FA，全角小写字母
	*	GBK/2：OxBOA1-F7FE, 收录 GB2312 汉字 6763 个，按原序排列
	*	GBK/3：Ox8140-AOFE，收录 CJK 汉字 6080 个
	*	GBK/4：OxAA40-FEAO，收录 CJK 汉字和增补的汉字 8160 个
	*	@ushChar
	*	@return bool
	**/
	inline bool IsValidDoubleChar(unsigned short ushChar)
	{
		return (ushChar >= 0xA3B0 && ushChar <= 0xA3B9)
			|| (ushChar >= 0xA3C1 && ushChar <= 0xA3DA)
			|| (ushChar >= 0xA3E1 && ushChar <= 0xA3FA)
			|| (ushChar >= 0xB0A0 && ushChar <= 0xF7FF)
			|| (ushChar >= 0x8140 && ushChar <= 0xA0FF)
			|| (ushChar >= 0xAA40 && ushChar <= 0xFEAF);
	}
 
	/**	
	*	半角字符转换成全角字符
	*	@chChar
	*	@return unsigned short
	**/
	inline unsigned short ToDoubleChar(char chChar)
	{
		//全角字符 - 半角字符 = 0xA380 
		return 0xA380 + chChar;
	}
 
	/**	
	*	全角字符转换成半角字符
	*	@ushChar
	*	@return char
	**/
	inline char ToSingleChar(unsigned short ushChar)
	{
		//全角字符 - 半角字符 = 0xA380 
		return ushChar - 0xA380;
	}
 
	/**	
	*	全角字符从小写字母转换成大写字母:两者差0x0020(32)
	*	@ushChar
	*	@return unsigned short
	**/
	inline unsigned short ToUpperChar(unsigned short ushChar)
	{
		if (ushChar >= 0xA3E1 && ushChar <= 0xA3FA)
			return ushChar - 0x0020;
 
		return ushChar;
	}
 
	/**	
	*	全角字符从大写字母转换成小写字母,两者差0x0020(32)
	*	@ushChar
	*	@return unsigned short
	**/
	inline unsigned short ToSmallChar(unsigned short ushChar)
	{
		if (ushChar >= 0xA3C1 && ushChar <= 0xA3DA)
			return ushChar + 0x0020;
 
		return ushChar;
	}
 
	/**
	*	把文本字符串转换成全角字符中的预处理
	*	@pchSrc			原文本字符串
	*	@pchDest		目的字符串
	*	@szLength		原文本字符串长度
	*	@return	size_t
	**/
	inline size_t PreProcess(const char* pchSrc, char* pchDest, size_t szLength)
	{
		const char* pchSrcPos = pchSrc;
		char* pchDestPos = pchDest;
 
		//判断字符串是否越界
		while(pchSrcPos < pchSrc + szLength)
		{
			//判断是单字符
			if (IsSingleChar(*pchSrcPos))
			{
				//判断是否是字母与数字
				if (IsValidSingleChar(*pchSrcPos))
				{
					unsigned short ushChar = ToDoubleChar(*pchSrcPos);
					ushChar = ntohs(ToUpperChar(ushChar));
					memcpy(pchDestPos, &ushChar, 2);
					pchDestPos += 2;
				}
 
				pchSrcPos++;
			}
			//判断是双字符
			else
			{
				//只有一个单字符(最后-最前)
				if (pchSrc + szLength - pchSrcPos < 2)
					break;
 
				//用无符号的短整型存储一个中文字符或宽字符
				unsigned short ushChar;
				memcpy(&ushChar, pchSrcPos, 2);
 
				//将一个无符号短整型数从主机字节顺序转换为网络字节顺序
				ushChar = htons(ToUpperChar(ushChar));
 
				if (IsValidDoubleChar(ushChar))
				{
					//将一个无符号短整型数从网络字节顺序转换为主机字节顺序
					ushChar = ntohs(ToUpperChar(ushChar));
					memcpy(pchDestPos, &ushChar, 2);
					pchDestPos += 2;
				}
 
				pchSrcPos += 2;
			}
		}
 
		return pchDestPos - pchDest;
	}
 
	/**
	*	把全角字符串转换成半角字符串的预处理
	*	@pchSrc			原文本字符串
	*	@pchDest		目的字符串
	*	@szLength		原文本字符串长度
	*	@return	size_t
	**/
	inline size_t ToHalfPreProcess(const char* pchSrc, char* pchDest, size_t szLength)
	{
		const char* pchSrcPos = pchSrc;
		char* pchDestPos = pchDest;
 
		//判断字符串是否越界
		while(pchSrcPos < pchSrc + szLength)
		{
			//用无符号的短整型存储一个中文字符或宽字符
			unsigned short ushChar = 0;
			//中文转换成无符号的短整型的好方法
			memcpy(&ushChar, pchSrcPos, 2);
			ushChar = htons(ushChar);
 
			//判断是否是大写的英文和数字
			if ((ushChar >= 0xA3C1 && ushChar <= 0xA3DA) || 
				(ushChar >= 0xA3B0 && ushChar <= 0xA3B9) ||
				(ushChar == 0xA3A0))
			{
				ushChar = ToSmallChar(ushChar);
				char chChar = ToSingleChar(ushChar);
				memcpy(pchDestPos, &chChar, 1);
				pchDestPos += 1;
			} 
			else
			{
				//只有一个单字符(最后-最前)
				if (pchSrc + szLength - pchSrcPos < 2)
					break;
 
				//用无符号的短整型存储一个中文字符
				ushChar = ntohs(ushChar);
				memcpy(pchDestPos, &ushChar, 2);
				pchDestPos += 2;
			}
 
			pchSrcPos += 2;
		}
 
		return pchDestPos - pchDest;
	}
 
};
 
 
/***************************************************
*	Original Filename: 		wm.cpp
*	Created/Modified: 		Andy_guo
*	Date:					2009/11/22	
*	Main Purpose:			WM算法
*	Comments:	
****************************************************/
#include "WM.h"
 
/****************************************************/
CWM::CWM(void)
{
	//从配置文件中加载关键词
	m_pWmStruct = new WMSTRUCT;
	memset(m_pWmStruct, 0, sizeof(WMSTRUCT));
 
	m_pWmStruct->plist = NULL;
	m_pWmStruct->msPatArray = NULL;
	m_pWmStruct->msNumArray = NULL;
	m_pWmStruct->msHash = NULL;
	m_pWmStruct->msShift = NULL;
	m_pWmStruct->msPrefix = NULL;
	m_pWmStruct->msSmallest = MAXPATTERN - 1;
 
	//加载模式
	LoadPatternToArray(m_pWmStruct);
 
	//字符串哈希值从小到大排列
	Sort(m_pWmStruct);
 
	//建立shift移动表
	CreateShiftTable(m_pWmStruct);
 
	//Hash哈希表的建立
	CreateHashTable(m_pWmStruct);
 
	//建立prefix前缀表
	CreatePrefixTable(m_pWmStruct);
}
 
CWM::~CWM(void)
{
	//释放WM综合结构体
	delete m_pWmStruct;
	m_pWmStruct = NULL;
}
 
/**********************************************
*功  能: 获取指定文件名路径
*参  数: const char*	strFileName		文件名
*	     char*			strFilePath		文件名路径
*返回值:								空
***********************************************/
#if 0
void CWM::GetFilePath(const char* strFileName, char* strFilePath)
{
	//文件路径
	CString pathFile;
 
	//取当前运行模块全路径
	GetModuleFileName(NULL, pathFile.GetBuffer(MAX_PATH), MAX_PATH);
	pathFile.ReleaseBuffer(MAX_PATH);
 
	//返回最后匹配字符序号
	int nIndex = pathFile.ReverseFind('\\');
 
	//取部分路径
	pathFile = pathFile.Left(nIndex);
 
	//取目的文件路径
	pathFile = pathFile + _T("\\") + _T(strFileName);
 
	//拷贝目的文件路径
	memcpy(strFilePath, pathFile.GetBuffer(pathFile.GetLength()), pathFile.GetLength());
	pathFile.ReleaseBuffer();
 
	return;
}
#endif
 
/****************************************************/
//从配置文件中加载关键词
int CWM::LoadPatternToArray(WMSTRUCT* pWmStruct)
{
	//分配WM内存空间
	if (pWmStruct == NULL)
	{
		pWmStruct = new WMSTRUCT;
		memset(pWmStruct, 0, sizeof(WMSTRUCT));
	}
 
#if 1
	int ch = 0; 
	char pchDest[64] = {0};
	//打开文件<关键词.txt>
	FILE* pFile = fopen(".\\关键词.txt","r");
 
	int i = 0;
	//读取文件
	while(!feof(pFile))
	{
		//读入一个数据
		ch = fgetc(pFile);
		if(ch != '\n')
		{
			pchDest[i++] = (char)ch; 
			continue;
		}
		else
			i = 0;
 
		//对关键词预处理
		char pchTemp[64] = {0};
		int size = CWM::PreProcess(pchDest, pchTemp, strlen(pchDest) + 1);
		strcpy_s(pchDest, pchTemp);
 
		//分配模式内存空间
		WMPATTERNSTRUCT* pPatternStruct = new WMPATTERNSTRUCT;
		if (!pPatternStruct) return -1;
		memset(pPatternStruct, 0, sizeof(WMPATTERNSTRUCT));
 
		//给节点赋值
		pPatternStruct->psPat = new char[strlen(pchDest) + 1];
		memset(pPatternStruct->psPat, 0, strlen(pchDest) + 1);
		strcpy_s(pPatternStruct->psPat, strlen(pchDest) + 1, pchDest);
		pPatternStruct->psLen = strlen(pchDest);
 
		//并把此模式加入链表
		pPatternStruct->next = pWmStruct->plist;
		pWmStruct->plist = pPatternStruct;
 
		//更新WM结构体值
		pWmStruct->msNumPatterns++;
		if (pPatternStruct->psLen < (unsigned)pWmStruct->msSmallest)
		{
			pWmStruct->msSmallest = pPatternStruct->psLen;
		}
 
		//清空数组
		memset(pchDest, 0, 64);
	} 
#else
	int ch = 0; 
	char pchDest[32] = {0};
	//打开文件<关键词.txt>
	FILE* pFile = fopen(".\\关键词.txt","r");
 
	//读取文件
	while(fgets(pchDest, 32, pFile) != NULL)
	{
		//分配模式内存空间
		WMPATTERNSTRUCT* pPatternStruct = new WMPATTERNSTRUCT;
		if (!pPatternStruct) return -1;
		memset(pPatternStruct, 0, sizeof(WMPATTERNSTRUCT));
 
		//给节点赋值
		pPatternStruct->psPat = new char[strlen(pchDest) + 1];
		memset(pPatternStruct->psPat, 0, strlen(pchDest) + 1);
		strcpy_s(pPatternStruct->psPat, strlen(pchDest) + 1, pchDest);
		pPatternStruct->psLen = strlen(pchDest);
		printf("%s\n", pPatternStruct->psPat);
		printf("%d\n", pPatternStruct->psLen);
 
		//并把此模式加入链表
		pPatternStruct->next = pWmStruct->plist;
		pWmStruct->plist = pPatternStruct;
 
		//更新WM结构体值
		pWmStruct->msNumPatterns++;
		if (pPatternStruct->psLen < (unsigned)pWmStruct->msSmallest)
		{
			pWmStruct->msSmallest = pPatternStruct->psLen;
		}
 
		//清空数组
		memset(pchDest, 0, 32);
	} 
#endif
 
	//分配模式数组内存空间
	pWmStruct->msPatArray = new WMPATTERNSTRUCT[sizeof(WMPATTERNSTRUCT) * pWmStruct->msNumPatterns];
	if (!pWmStruct->msPatArray)
	{
		printf("ERROR：分配内存空间失败！\n");
		return -1;
	}
 
	//有相同哈希散列值数组空间
	pWmStruct->msNumArray = new unsigned short[sizeof(short) * pWmStruct->msNumPatterns];
	if(!pWmStruct->msNumArray)
	{
		printf("ERROR：分配内存空间失败！\n");
		return -1;
	}
 
	//遍历模式链表,并拷贝到模式数组
	WMPATTERNSTRUCT* pList = NULL;
	int kk;
	for(kk = 0, pList = pWmStruct->plist; 
		pList != NULL && kk < pWmStruct->msNumPatterns; 
		pList = pList->next)
	{
		memcpy(&pWmStruct->msPatArray[kk++], pList, sizeof(WMPATTERNSTRUCT));
	}
 
	return 0;
}
 
/****************************************************/
//字符串哈希值从小到大排列
void CWM::Sort(WMSTRUCT* pWmStruct)
{
	//取所有模式的最小值
	int m = pWmStruct->msSmallest, B = 4;
	unsigned char* temp;
 
	for(int i = pWmStruct->msNumPatterns - 1, flag = 1; i > 0 && flag; i--)
	{
		flag = 0;
		for(int j = 0; j < i; j++)
		{
			//后面的比前面还要小，则交换两者
			if(CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[j + 1].psPat[m - B]) 
				< CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[j].psPat[m - B]))
			{
				flag = 1;
				temp = (unsigned char*)pWmStruct->msPatArray[j + 1].psPat;
				pWmStruct->msPatArray[j + 1].psPat = pWmStruct->msPatArray[j].psPat;
				pWmStruct->msPatArray[j].psPat = (char*)temp;
			}
		}
	}
}
 
/****************************************************/
//建立shift移动表
void CWM::CreateShiftTable(WMSTRUCT* pWmStruct)
{
	//要考虑的一块字符串的大小
	int B = 4;
	//所有模式的最小长度
	int m = pWmStruct->msSmallest;
 
	//建立移动表空间
	pWmStruct->msShift = new unsigned char[SHIFTTABLESIZE * sizeof(char)];
	if(!pWmStruct->msShift) return;
	memset(pWmStruct->msShift, 0, SHIFTTABLESIZE * sizeof(char));
 
	//当模式数量少时,取(B = 2),移动表所有初始值为(m - B + 1)
	//显然,与任何模式都不匹配时值为(m - B + 2)
	for(int i = 0; i < SHIFTTABLESIZE; i++)
		pWmStruct->msShift[i] = (unsigned)(m - B + 2);
 
	//为每个大小为B的字符串映射一个入口
	for(int i = 0; i < pWmStruct->msNumPatterns; i++)
	{
		for(int k = 0; k < m - 2; k++)
		{
			//大小为B的字符串与模式相比,要移动的位数
			//如:(中国)与(中国人)相比,移动2位;(国人)与(中国人)相比,移动0位
			unsigned short nShift = (unsigned short)(m - B - k);
 
#if 1
			//为每个大小为B的字符串匹配一个整数作为移动表的索引
			//匹配时,移动表索引值与哈希表的索引值相同
			unsigned short nIndex = CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[i].psPat[k]);
#else
			//为每个大小为B的字符串匹配一个整数作为移动表的索引
			//匹配时,移动表索引值与哈希表的索引值相同
			unsigned short nIndex = pWmStruct->msPatArray[i].psPat[k] << 4
				| pWmStruct->msPatArray[i].psPat[k + 2];
#endif
 
			//与模式匹配时值shift[i]为(m - q),即到q时要移动的距离
			//如：文本ca与模式cat匹配时，要移动1个距离;at与模式cat匹配时，要移动0个距离
			if(nShift < pWmStruct->msShift[nIndex])
				pWmStruct->msShift[nIndex] = nShift;
 
			k++;
		}
	}
 
	return;
}
 
/****************************************************/
//建立prefix前缀表
void CWM::CreatePrefixTable(WMSTRUCT* pWmStruct)
{
	//建立前缀表空间
	pWmStruct->msPrefix = new HASH_TYPE[sizeof(HASH_TYPE) * (pWmStruct->msNumPatterns)];
	if(!pWmStruct->msPrefix) return;
 
	for(int i = 0; i < pWmStruct->msNumPatterns; i++)
	{
		pWmStruct->msPrefix[i] = CWM::HASH16((unsigned char*)pWmStruct->msPatArray[i].psPat);
	}
 
	return;
}
 
/****************************************************/
//哈希表的建立，计算有多少个不同哈希值，且从小到大
int CWM::CreateHashTable(WMSTRUCT* pWmStruct)
{
	unsigned sindex, hindex, nInGroup;
	int m = pWmStruct->msSmallest;
	int B = 4;
 
	//分配内存空间
	pWmStruct->msNumHashEntries = HASHTABLESIZE;
	pWmStruct->msHash = new HASH_TYPE[sizeof(HASH_TYPE) * pWmStruct->msNumHashEntries];
	if(!pWmStruct->msHash)
	{
		printf("ERROR：分配内存空间出错！\n");
		return -1;
	}
 
	//给哈希表的条目初始化为-1
	for(int i = 0; i < (int)pWmStruct->msNumHashEntries; i++)
	{
		pWmStruct->msHash[i] = (HASH_TYPE) - 1;
	}
 
	//遍历模式列表
	for(int i = 0; i < pWmStruct->msNumPatterns; i++)
	{
		//计算最后B(在这B=4)个字符的哈希值为i
		hindex = CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[i].psPat[m - B]);
		sindex = pWmStruct->msHash[hindex] = i;
 
		//计算最后B个字符的哈希值相等的个数
		nInGroup = 1;
		while(++i < pWmStruct->msNumPatterns && 
			hindex == CWM::HASH16((unsigned char*)&pWmStruct->msPatArray[i].psPat[m - B]))
			nInGroup++;
 
		//把有相同哈希值的个数放入模式数组中
		pWmStruct->msNumArray[sindex] = nInGroup;
		i--;
	}
 
	return 0;
}
 
/********************************************************
* 功 能: WM算法模式匹配
* 参 数: unsigned char*		pchSrcText		要过滤的文本内容
*		 int				nTextLen		原文本内容长度
*		 WMPATTERNSTRUCT*	pList			返回匹配的字符
*返回值:									无
*********************************************************/
int CWM::WMPatternMatch(unsigned char* pchSrcText, int nTextLen, WMPATTERNSTRUCT** pList)
{
	//预处理后的文本缓存
	char pchDestText[1024] = {0};
	memset(pchDestText, 0, 1024);
	nTextLen = strlen((char*)pchSrcText) + 2;
 
	//预处理文本,减少循环次数
	int nDestTextLen = PreProcess((char*)pchSrcText, pchDestText, nTextLen);
 
	//取WM综合结构体
	WMSTRUCT* pWmStruct = m_pWmStruct;
 
	//文本的右边界(尾)
	unsigned char* TextEnd = (unsigned char*)(pchDestText + nDestTextLen);
 
	//若文本比最小的模式的长度还小，退出
	if(nDestTextLen < pWmStruct->msSmallest)
		return -1;
 
	//模式块窗口尾
	unsigned char* windowEnd = (unsigned char*)(pchDestText + pWmStruct->msSmallest);
 
	//1.计算文本当前被扫描的B个字符的哈希值h(从t[m-B+1]...t[m])
	for(unsigned char* windowBgn = (unsigned char*)pchDestText; windowEnd <= TextEnd; windowBgn++, windowEnd++)
	{
		//取移动表shift[i]的值(nShift),若为0，则有匹配
		int nShift = pWmStruct->msShift[*windowBgn << 4 | *(windowEnd - 2)];
 
		//2.检查shift[i]的值nShift,不为0,没有匹配
		while(nShift)
		{
			windowBgn += nShift;
			windowEnd += nShift;
 
			//窗口的边界超出文本尾
			if(windowEnd > TextEnd)
				return -1;
 
			//寻找下一个匹配
			nShift = pWmStruct->msShift[*windowBgn << 4 | *(windowEnd - 2)];
		} 
 
		//移动值为0,找到匹配,取对应的散列值(nIndex)
		int nIndex = pWmStruct->msHash[*windowBgn << 4 | *(windowEnd - 2)];
		if(nIndex  == (HASH_TYPE) - 1) 
			continue;
 
		WMPrefixMatch(nIndex, (unsigned char*)pchDestText, windowBgn, pList);
 
		windowBgn++;
		windowEnd++;
	}
 
	return 0;
}
 
/**********************************************
*功  能: 后缀哈希值相同，比较前缀以及整个字符匹配
*参  数: int			nIndex		散列值
*	     unsigned char* pchDestText	文本初始内容
*	     unsigned char* windowBgn	有匹配的文本头
*返回值:							无
***********************************************/
int CWM::WMPrefixMatch(int nIndex, unsigned char* pchDestText, unsigned char* windowBgn,WMPATTERNSTRUCT** pList)
{
	//取WM综合结构体
	WMSTRUCT* pWmStruct = m_pWmStruct;
 
	//取有相同哈希值头与尾
	WMPATTERNSTRUCT* pPatternBegin = &pWmStruct->msPatArray[nIndex];
	WMPATTERNSTRUCT* pPatternEnd = pPatternBegin + pWmStruct->msNumArray[nIndex];
 
	//3.计算文本前缀哈希值
	int text_prefix = CWM::HASH16(windowBgn);
 
	//4.检查每个满足(HASH[h] <= P < HASH[h+1])的模式P
	for( ; pPatternBegin < pPatternEnd; pPatternBegin++)
	{
		if(pWmStruct->msPrefix[nIndex++] != text_prefix)
			continue;
		else
			//5.当PREFIX[P]=text_prefix,与原文本比较
		{
			unsigned char* pPatternTxt = (unsigned char*)pPatternBegin->psPat;
			unsigned char* pTxt = windowBgn;
 
			//对文本和模式进行直接检查
			while(*(pPatternTxt++) == *(pTxt++) && *(pTxt - 1) != '\0');
 
			//取到匹配的模式
			if(*(pPatternTxt - 1) == '\0')
			{
				printf("Matched pattern is：%s\n", pPatternBegin->psPat);
				//保存已经匹配的模式内容
				WMPATTERNSTRUCT* pMatchedPtn = new WMPATTERNSTRUCT;
				memset(pMatchedPtn, 0, sizeof(WMPATTERNSTRUCT));
 
				pMatchedPtn->psPat = new char[strlen(pPatternBegin->psPat) + 1];
				memset(pMatchedPtn->psPat, 0, strlen(pPatternBegin->psPat) + 1);
				strcpy_s(pMatchedPtn->psPat, strlen(pPatternBegin->psPat) + 1, pPatternBegin->psPat);
				pMatchedPtn->next = *pList;
				*pList = pMatchedPtn;
			}
 
		}
 
	}
 
	return 0;
}
 
/***************************************************
*功  能: 用指定的字符串替换文本中出现的要替换的字符串
*参  数: char* pchInput	 	含特殊字符的字符串
*		 char* pchOutput	转换后的字符串
*		 char* pSrc			要转换的特殊字符	
*		 char* pDst			要转换的目的字符
*返回值:					转换后的字符串
****************************************************/
char* CWM::Substitute(char* pchInput, char* pchOutput, char* pSrc, char* pDst)
{
	char *pchSrc, *pchDst, *pCursor;
	int nSrcLen, nDstLen, nLen;
 
	// 指向输入字符串的游动指针.
	pchSrc = pchInput;
	// 指向输出字符串的游动指针.
	pchDst = pchOutput;
	// 计算被替换串和替换串的长度.
	nSrcLen = strlen(pSrc);
	nDstLen = strlen(pDst);
 
	//查找pchSrc,返回指向字符串中第一次出现替换串的位置指针(找不到则返回null).
	pCursor = strstr(pchSrc, pSrc);
	if(pCursor)
	{
		// 找到
		while(pCursor) 
		{
			// 计算被替换串前边字符串的长度.
			nLen = (int)(pCursor - pchSrc);
			// 复制游标指针前的字符串
			memcpy(pchDst, pchSrc, nLen);
			// 复制替换字符
			memcpy(pchDst + nLen, pDst, nSrcLen/2 + nSrcLen%2);
			// 指针跳过被替换串
			pchSrc = pCursor + nSrcLen;
			// 调整指向输出串的指针位置
			pchDst = pchDst + nLen + nSrcLen/2 + nSrcLen%2;
			// 继续查找
			pCursor = strstr(pchSrc, pSrc);
		}
		// 复制剩余字符串.
		strcpy(pchDst, pchSrc);
	}
	else
	{
		// 没有找到则原样复制.
		strcpy(pchDst, pchSrc);
	}
 
	return pchDst;
}