acbyhune.cpp

用C++实现的AC字符串匹配算法

#include <stdio.h>
#include <conio.h>
#include <string>
#include <pcap.h>
using namespace std;

#define MAX_STATE	100			//自动机最大状态数
#define MAX_SYMBOL	256			//匹配的字符数 可以匹配所有的ASCII码
#define MAX_MODE	20	


int outputsym[MAX_STATE];
int DFA[MAX_STATE][MAX_SYMBOL];
int F[MAX_STATE];
int statecount=1;
int cur_state;
string outputdata[MAX_STATE];
void mygo()
{	bool start=true;
	u_int modecount=0;
	u_int currentstate;
	string str="";
	u_char c;
	printf("Enter the set of modes：");
	while((c=getchar())!=(u_int)'\n')
	{	if(c!=(u_int)' ')
		{	if(start)
			{	start=false;
				modecount++;
				currentstate=0;
				str="";
			}
			str+=c;
			if(DFA[currentstate][c]==-1)
			{	DFA[currentstate][c]=statecount;
				currentstate=statecount;
				statecount++;
			}
			else
				currentstate=DFA[currentstate][c];

		}
		else
		{	if(modecount>=MAX_MODE)
			{	printf("The max size of the modes is %d!\n",MAX_MODE);
				break;
			}
			outputsym[currentstate]=1;
			outputdata[currentstate]=str;
			start=true;
		
		}
	}	
			outputsym[currentstate]=1;
			outputdata[currentstate]=str;
}

void fail()
{	u_int i,j,t;
	for(i=1;i<statecount;i++)
		for(j=0;j<MAX_SYMBOL;j++)
		{	t=DFA[i][j];
			if(t!=-1)
			{	F[t]=DFA[F[i]][j];
			}
		}
}
void init()
{	int i,j;
	for(i=0;i<MAX_STATE;i++)
		for(j=0;j<MAX_SYMBOL;j++)
			DFA[i][j]=-1;
	for(i=0;i<MAX_STATE;i++)
	{	outputsym[i]=0;
		outputdata[i]="";
		F[i]=0;}
	
	cur_state=0;
	mygo();
	fail();
}
bool AC(u_char c,bool flag)
{	bool rtflag=false;
	if(c<MAX_SYMBOL)
	{	
//		if(outputsym[F[temp]]==1)
//			printf("Match string with %s\n",&outputdata[F[temp]][0]);
		if(DFA[cur_state][c]!=-1)
		{	
			cur_state=DFA[cur_state][c];
			if(outputsym[cur_state]==1)
			{	printf("Match string with %s\n",&outputdata[cur_state][0]);
				rtflag=true;
			}
		}
		else
		{	while(DFA[cur_state][c]==-1)
			{	if(cur_state==0&&DFA[cur_state][c]==-1)
					break;
				cur_state=F[cur_state];
				if(outputsym[cur_state]==1)
				{		printf("Match string with %s\n",&outputdata[cur_state][0]);
						rtflag=true;}
			
			}
			if(DFA[cur_state][c]!=-1)
			{	
				cur_state=DFA[cur_state][c];
				if(outputsym[cur_state]==1)
				{	printf("Match string with %s\n",&outputdata[cur_state][0]);
					rtflag=true;
				}
			}
		}
	
	}
	return rtflag;
}
void main()
{	u_char c;
	init();
	printf("Enter the string in which to match:");
	do
	{	c=getchar();
		AC(c,false);
	}while(c!=(u_int)'\n');
}