多模匹配 Wu-Manber算法源码

【模式匹配】之——多模匹配 Wu-Manber算法源码，对应文章地址： http://blog.csdn.net/sun2043430/article/details/8875566

#include “WuManber.h“
#include 

typedef unsigned short      WORD;

#define WORD_SIZE 65536
#define M_VALUE 5
#define B_VALUE 2
 
typedef struct _NODE
{
    _NODE       *pNext;     //next node point
    const char  *pPattern;  //pattern string
    WORD        wPrefix;    //prefix value
}NODE *PNODE;

unsigned char   *g_ShiftTable   = NULL;
PNODE           *g_pNode        = NULL;

void TestWuManber（）;
void TestWuManber2（）;
bool BuildShiftTable（vector vecPattern）;
bool InsertNode（WORD wdHash const char *pPattern WORD wPrefix）;
void Release（）;
void WuManberSearch（const char *pDest）;
void ReportMatch（int nFindEnd const char *pPattern）;

int main（）
{
    TestWuManber（）;
    TestWuManber2（）;

    return 0;
}

void TestWuManber（）
{
    printf（“0         1         2         3         4\r\n“）;
    printf（“01234567890123456789012345678901234567890\r\n“）;
    bool b;
    char text[] = “text is abcde 12345“;
    vector vecPattern;
    vecPattern.push_back（“abcde“）;
    vecPattern.push_back（“12345“）;
    vecPattern.push_back（“ab345“）;
    vecPattern.push_back（“12cde“）;
    WuManber wumanber;
    wumanber.Initialize（vecPattern true）;
    b = wumanber.Search（strlen（text） text vecPattern）;
    return;
}

void TestWuManber2（）
{
    printf（“0         1         2         3         4         5         6\r\n“）;
    printf（“0123456789012345678901234567890123456789012345678901234567890\r\n“）;
    char text[] = “text is abcdef 123456 abx456 12xdef 12cdef ab3456 ab3457“;
    printf（“%s\r\n“ text）;
    vector vecPattern;
    vecPattern.push_back（“abcdef“）;
    vecPattern.push_back（“123456“）;
    vecPattern.push_back（“ab3456“）;
    vecPattern.push_back（“12cdef“）;
    BuildShiftTable（vecPattern）;
    WuManberSearch（text）;
    Release（）;
    return;
}

//the length of each string in vector must longer then M_VALUE
bool BuildShiftTable（vector vecPattern）
{
    bool bRet = false;
    //how long the shift table?  the range of hash value.
    //we use the two characters combine the hash value
    //so the range of hash value is 0 to 65535 need 64k size to store
    g_ShiftTable = new unsigned char[WORD_SIZE];
    if （NULL == g_ShiftTable）
    {
        goto Exit0;
    }

    g_pNode = new PNODE[WORD_SIZE];
    if （NULL == g_pNode）
    {
        goto Exit0;
    }

    for （int i = 0; i < WORD_SIZE; i++）
    {
        g_ShiftTable[i] = M_VALUE - 1;
    }
    memset（g_pNode 0 WORD_SIZE * sizeof（g_pNode[0]））;

    for （unsigned int i = 0; i < vecPattern.size（）; i++）
    {
        for （int j = 0; j < M_VALUE - B_VALUE + 1; j++）
        {
            WORD wdHash = *（WORD *）（&vecPattern[i][M_VALUE-1 - j - 1]）;
            if （g_ShiftTable[wdHash] > j）
                g_ShiftTable[wdHash] = j;
            if （0 == j）// need save prefix hash value for each pattern but maybe more than one
            {
         

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-05-02 16:51  wu-manber\
     目录           0  2013-05-02 16:51  wu-manber\wu-manber\
     文件        1247  2013-04-24 23:08  wu-manber\wu-manber.sln
     文件        5302  2013-05-02 16:24  wu-manber\wu-manber\main.cpp
     文件        6823  2013-04-30 23:28  wu-manber\wu-manber\WuManber.cpp
     文件        2218  2013-04-11 13:17  wu-manber\wu-manber\WuManber.h
     文件        7058  2013-04-24 22:43  wu-manber\wu-manber\wu-manber.vcproj