AC算法和AC-BM算法

AC算法和ACBM算法 算法实现代码 相关论文（英文原版论文）

/*
**
** Multi-Pattern Search Engine
**
** Aho-Corasick State Machine -  uses a Deterministic Finite Automata - DFA
**
** Copyright （C） 2002 SourcefireInc.
** Marc Norton
**
**  
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License or
** （at your option） any later version.
**
** This program is distributed in the hope that it will be useful
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not write to the Free Software
** Foundation Inc. 59 Temple Place - Suite 330 Boston MA 02111-1307 USA.
**
**
**   Reference - Efficient String matching: An Aid to Bibliographic Search
**               Alfred V Aho and Margaret J Corasick
**               Bell Labratories 
**               Copyright（C） 1975 Association for Computing MachineryInc
**
**   Implemented from the 4 algorithms in the paper by Aho & Corasick
**   and some implementation ideas from ‘Practical Algorithms in C‘
**
**   Notes:
**     1） This version uses about 1024 bytes per pattern character - heavy  on the memory. 
**     2） This algorithm finds all occurrences of all patterns within a  
**        body of text.
**     3） Support is included to handle upper and lower case matching.     
**     4） Some comopilers optimize the search routine well others don‘t this makes all the difference.
**     5） Aho inspects all bytes of the search text but only once so it‘s very efficient
**        if the patterns are all large than the Modified Wu-Manbar method is often faster.
**     6） I don‘t subscribe to any one method is best for all searching needs
**        the data decides which method is best
**        and we don‘t know until after the search method has been tested on the specific data sets.
**        
**
**  May 2002  : Marc Norton 1st Version  
**  June 2002 : Modified interface for SNORT added case support
**  Aug 2002  : Cleaned up comments and removed dead code.
**  Nov 22002: Fixed queue_init（）  added count=0
**              
**  Wangyao : wangyao@cs.hit.edu.cn
**
**  Apr 242007: WangYao Combined Build_NFA（） and Convert_NFA_To_DFA（） into Build_DFA（）;
**				 And Delete Some redundancy Code 
**	
*/  

#include 
#include 
#include 
#include 
#include “acsmx.h“

#define MEMASSERT（ps） if（!p）{fprintf（stderr“ACSM-No Memory: %s!\n“s）;exit（0）;}

/*Define the number of the linewhen match a keyword*/
extern int nline=1;

/*
* Malloc the AC Memory
*/ 
static void *AC_MALLOC （int n） 
{
	void *p;
	p = malloc （n）;

	return p;
}

/*
*Free the AC Memory
*/ 
static void AC_FREE （void *p） 
{
	if （p）
		free （p）;
}


/*
*    Simple QUEUE NODE
*/ 
typedef struct _qn

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

     文件      12349  2007-05-10 14:49  acsmx.c

     文件       2323  2007-05-10 14:49  acsmx.h

     文件       1057  2007-05-10 14:49  entry.c

     文件      13178  2005-03-10 21:15  acbm\ac_bm.c

     文件       1191  2005-03-10 21:15  acbm\ac_bm.h

     目录          0  2009-04-22 16:03  acbm

     文件     703360  2009-03-16 16:37  （AC-BM）getPDF.pdf

     文件    1191717  2009-02-13 16:29  （BM）A Fast String Searching Algorithm.pdf

     文件     147821  2009-03-04 09:34  （BMH）stringsearch.pdf

     文件     733782  2009-03-16 10:04  Aho-Corasick.pdf

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

              2806778                    10