一、概述

二、AC算法思想

图2.1

图2.2

图2.3

图2.4

图2.5

图2.6

三、字典树tire的构造

图3.1

四、搜索路径的确定

附录：

附1：

图 附1.1

附2：AC算法的伪代码实现描述

q := 0; // initial state (root)
for i := 1 to m do
    while g(q,T) = NULL do
        q := f(q); // 回溯
    q := g(q,T); // 前进
    node:=q;
    while(node!=root){
        if flag(node) exist ; then print i, out(node);
        node = f(node);   //查找回溯节点
    }
end for;

附3：

/*
程序说明：多模式串匹配的AC自动机算法
自动机算法可以参考《柔性字符串匹配》里的相应章节，讲的很清楚
*/

#include <stdio.h>
#include <string.h>

const  int MAXQ = 500000+10;
const  int MAXN = 1000000+10;
const  int MAXK = 26;  //自动机里字符集的大小 
struct  TrieNode
{
	TrieNode* fail;
	TrieNode* next[MAXK];
	bool danger;   //该节点是否为某模式串的终结点 
	int  cnt;    //以该节点为终结点的模式串个数 
	TrieNode()
	{
		fail = NULL;
		memset(next, NULL, sizeof(next));
		danger = false;
		cnt = 0;
	}
}*que[MAXQ], *root;
//文本字符串
char  msg[MAXN];
int   N;
void  TrieInsert(char *s)
{
	int  i = 0;
	TrieNode *ptr = root;
	while(s)
	{
		int  idx = s-'a';
		if(ptr->next[idx] == NULL)
			ptr->next[idx] = new TrieNode();
		ptr = ptr->next[idx];
		i++;
	}
	ptr->danger = true;
	ptr->cnt++;
}

void  Init()
{
	int  i;
	char  s[100];
	root = new TrieNode();
	
	printf("输入模式串数量：");
	scanf("%d", &N);
	for(i = 0; i < N; i++)
	{
		printf("输入第%d个模式串（共%d个）：",i,N);
		scanf("%s", s);
		TrieInsert(s);
	}
}

void  Build_AC_Automation()
{
	int  rear = 1, front = 0, i;
	que[0] = root;
	root->fail = NULL;
	while(rear != front)
	{
		TrieNode *cur = que[front++];
		for(i = 0; i < 26; i++)
			if(cur->next != NULL)
			{
				if(cur == root)
					cur->next->fail = root;
				else
				{
					TrieNode *ptr = cur->fail;
					while(ptr != NULL)
					{
						if(ptr->next != NULL)
						{
							cur->next->fail = ptr->next;
							if(ptr->next->danger == true)
								cur->next->danger = true;
							break;
						}
						ptr = ptr->fail;
					}
					if(ptr == NULL) cur->next->fail = root;
				}
				que[rear++] = cur->next;
			}
	}
}
int  AC_Search()
{
	int  i = 0, ans = 0;
	TrieNode *ptr = root;
	while(msg)
	{
		int  idx = msg-'a';
		while(ptr->next[idx] == NULL && ptr != root) ptr = ptr->fail;
		ptr = ptr->next[idx];
		if(ptr == NULL) ptr = root;
		TrieNode *tmp = ptr;
		while(tmp != NULL )&& tmp->cnt != -1)
		{
			ans += tmp->cnt;	//统计文本中出现过的不同模式串数量
			tmp->cnt = -1;//对于每个模式串的出现只计算一次，如统计所有出现则应注释该行
			tmp = tmp->fail;
		}
		i++;
	}
	return  ans;
}
int  main()
{
	int  T;
	printf("输入测试次数：");
	scanf("%d", &T);
	while(T--)
	{
		Init();
		Build_AC_Automation();
		//文本 
		printf("输入匹配文本：");
		scanf("%s", msg);
		printf("%dn", AC_Search());
	}
	getchar();
    return 0;
}

 下载：

 摘自snort的AC算法源码实现等资料下载：点击下载此文件

相关文章:

卡巴斯基2009、2010、2011激活码授权文件key下载 自动机理论、语言和计算导论课后习题答案下载 孙家啸等翻译 机械工业出版社 windows平台上运行的unix模拟环境cygwin：cygwin的安装配置与使用介绍 精确单字符串匹配BM算法及其在snort中的C语言实现代码解析 分布式文件系统Andrew file system运行机制简介 什么是UTM：统一威胁管理(Unified Threat Management)简介 Linux LVM逻辑卷管理详细介绍 LVM磁盘镜像同步备份：实现LVM镜像的详细方法与步骤 LVM+iSCSI磁盘远程镜像配置步骤 Linux CDP（连续性数据保护）实现方案、技术细节介绍及相关源码文档下载