WM（Wu-Manber）算法详解及C语言实现

WM(Wu-Manber)算法详解及C语言实现程序代码解析参考 可直接运行。

#include “wm.h“

#include 
#include 
#include 
#include 

extern int nline=1;
extern int nfound=0;
#define MAXN 10001 //模式串的最大长度MAXN - 1
#define MAXM 51//单词最大长度为MAXM - 1

/* ****************************************************************
    函数：void wmNew（）
	目的：创建一个模式串集合
	参数：
		无
    返回：
	    WM_STRUCT - 创建的模式串集
 ****************************************************************/
WM_STRUCT * wmNew（）
{
	WM_STRUCT *p=（WM_STRUCT *）malloc（sizeof（WM_STRUCT））;
	if（!p） return 0;
	p->msNumPatterns=0;//模式串的个数初始为0
	p->msSmallest=1000;//最短模式串的长度
	return p;
}

/* ****************************************************************
    函数：void wmFree（WM_STRUCT *）
	目的：释放模式串集占用空间
	参数：
		ps => 模式串集
    返回：
	    
 ****************************************************************/
void wmFree（WM_STRUCT *ps） //释放空间函数
{
	if（ps->msPatArray） //如果模式串集中存在子串，则先释放子串数组占用空间
	{
		if（ps->msPatArray->psPat） free（ps->msPatArray->psPat）;	//子串不为空，则释放
		free（ps->msPatArray ）;
	}
	if（ps->msNumArray） free（ps->msNumArray）;
	if（ps->msHash） free（ps->msHash）;
	if（ps->msPrefix） free（ps->msPrefix）;
	if（ps->msShift） free（ps->msShift）;
	free（ps）;
}

/* ****************************************************************
    函数：int wmAddPattern（WM_STRUCT *unsigned char *int ）
	目的：向模式串集ps中新增一个长度为m的子串q
	参数：
		ps => 模式串集
		q => 要新增的子串
		m => 子串长度
    返回：
	    int* - 新增成功0，失败-1
 ****************************************************************/
int wmAddPattern（WM_STRUCT *psunsigned char *qint m）
{
	WM_PATTERN_STRUCT *p;  //定义一个子串结构
	p=（WM_PATTERN_STRUCT *）malloc（sizeof（WM_PATTERN_STRUCT））;
	if（!p） return -1;

	p->psPat=（unsigned char*）malloc（m+1）; //据子串数组的长度分配空间
	memset（p->psPat+m01）;	//最后一个位置设置为结束字符“/0” 
	memcpy（p->psPatqm）; //拷贝q到子串结构数组中
	p->psLen=m; //子串长度赋值
	ps->msNumPatterns++; //模式串集的子串个数增1
	if（p->psLen < （unsigned）ps->msSmallest） ps->msSmallest = p->psLen; //重新确定最短字符串长度

	p->next=ps->plist; //将新增子串加入字符串集列表中。队列形式，新增在队列头部
	ps->plist=p;

	return 0;
}

/* ****************************************************************
    函数：static unsigned HASH16（unsigned char *）
	目的：对一串字符进行哈希计算。计算方式为：（（（*T）<<8） | *（T+1）），
	参数：
		T => 要哈希计算的字符串
    返回：
	    unsigned - 静态函数，返回对字符串T计算的哈希值
 ****************************************************************/
static unsigned HASH16（unsigned char *T）
{
	/*/
	printf（“T:%c\n“*（T））;
	getchar（）;
	printf（“T+1:%c\n“*（T+1））;
	getchar（）;
	printf（“T<<8:%c\n“（int）（（*T）<<8））;
	getchar（）;
	printf（“HASH16:%d\n“（（*T）<<8） | *（T+1））;
	getchar（）;
	//*/
	return （unsigned short） （（（*T）<<8） | *（T+1））; //对第一个字符左移8位，然后与第二个字符异或运算
}

/* ****************************************************************
    函数：sort（WM_STRUCT *）
	目的：对字符串集ps中的子串队列，根据子串串值的哈希值从小到大排序
	参数：
		ps => 模式串集
    返回：无
 ****************************************************************/
void sort（WM_STRUCT *ps）
{
	int m=ps->msSmallest; //获取最短子串长度
	int ij;
	unsigned char 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      10697  2011-01-17 10:52  wm.c

     文件       1403  2011-01-17 10:45  wm.h

     文件        263  2011-01-17 13:16  WM（Wu-Manber）算法详解及C语言实现程序代码解析参考 - 志文工作室 - 计算机技术学习博客.url

----------- ---------  ---------- -----  ----

                12363                    3