HDU ACM 2896病毒袭击->AC自动机

HDU ACM 2896病毒侵袭->AC自动机

分析：AC自动机，套用模版，保存每个网站的病毒，然后排序输出，最后统计网站数即可。

#include<iostream>
#include<queue>
using namespace std;

int VirusID[5];
#define LETTER_COUNT 128
class AC_Automation
{
private:
	struct Node
	{
		Node* fail;                  //失败指针
		Node* next[LETTER_COUNT];  //Tire树节点的子节点
		int id;                    //每个病毒的最后一个节点，为病毒id
		int webpos;                    //记录网站的id，避免病毒被重复查找
		Node()
		{
			fail=NULL;
			webpos=id=0;
			memset(next,NULL,sizeof(next));
		}
	};
	Node* m_sroot;

	void Delete(Node* p);
public:
	AC_Automation(){ m_sroot=(Node*)new Node();}
	~AC_Automation(){ Delete(m_sroot);}

	void AddWord(char* str,int id);      //添加病毒特征码,id为病毒id
	void Build_AC_Automation();
	int GetMatchingCount(char* str,int id);  //查找病毒,id为网站id
};

int AC_Automation::GetMatchingCount(char* str,int id)
{
	int cnt=0,index;
	Node* p,*temp;

	p=m_sroot;
	while(*str)
	{
		index=*str-' ';
		while(p->next[index]==NULL && p!=m_sroot) p=p->fail;
		p=p->next[index];
		p=(p==NULL)?m_sroot:p;

		temp=p;
		while(temp!=m_sroot && temp->webpos!=id)    //确保当前字符前面包含的所有单词都被匹配
		{
			if(temp->id) VirusID[++VirusID[0]]=temp->id;
			temp->webpos=id;
			temp=temp->fail;
		}
		str++;
	}
	return cnt;
}

void AC_Automation::Delete(Node* p)
{
	for(int i=0;i<LETTER_COUNT;i++)
		if(p->next[i]!=NULL)
			Delete(p->next[i]);
	delete p;
}

void AC_Automation::Build_AC_Automation()
{
	int i;
	Node *temp,*p;
	queue<Node*> q; //队列，用于BFS，建立失败指针

	m_sroot->fail=NULL;
	q.push(m_sroot);
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		p=NULL;
		for(i=0;i<LETTER_COUNT;i++)
		{
			if(temp->next[i]!=NULL)
			{
				if(temp==m_sroot) temp->next[i]->fail=m_sroot;
				else
				{
					p=temp->fail;
					while(p!=NULL)
					{
						if(p->next[i]!=NULL)
						{
							temp->next[i]->fail=p->next[i];
							break;
						}
						p=p->fail;
					}
					if(p==NULL) temp->next[i]->fail=m_sroot;
				}
				q.push(temp->next[i]);        //子节点如队列
			}
		}
	}
}

void AC_Automation::AddWord(char* str,int id)
{
	Node* p=m_sroot;
	int index;

	while(*str)
	{
		index=*str-' ';
		if(p->next[index]==NULL) p->next[index]=(Node*)new Node();
		p=p->next[index];
		str++;
	}
	p->id=id;             //单词的最后一个节点加1，单表新加入一个单词
}

void OutPut(int id)
{
	int i;

	sort(VirusID+1,VirusID+VirusID[0]+1);
	cout<<"web "<<id<<":";
	for(i=1;i<=VirusID[0];i++)
		cout<<" "<<VirusID[i];
	cout<<endl;
}

int main()
{
	int N,i,M;
	char a[202],b[10002];
	int sum;

	while(cin>>N)
	{
		AC_Automation ac_tuto;
		sum=0;
    	for(i=1;i<=N;i++)
		{
     		cin>>a;
    		ac_tuto.AddWord(a,i);
		}
    	ac_tuto.Build_AC_Automation();
    	cin>>M;
    	for(i=1;i<=M;i++)
		{
			VirusID[0]=0;
			cin>>b;
			ac_tuto.GetMatchingCount(b,i);
			if(VirusID[0])
			{
				OutPut(i);
				sum++;
			}
		}
		cout<<"total: "<<sum<<endl;
	}
	return 0;
}