HDU ACM 3065 病毒袭击持续中->AC自动机

HDU ACM 3065 病毒侵袭持续中->AC自动机

分析：AC自动机，注意该題是找单词出现的次数，因此在查询过程中不做限制，即查询过的不标记，因为所有出现情况都要计数，刚好利用了AC自动机特有fail指针。

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

char b[2000002];
#define LETTER_COUNT 128
int coun[1001];
char a[1001][60];

class AC_Automation
{
private:
	struct Node
	{
		Node* fail;                  //失败指针
		Node* next[LETTER_COUNT];  //Tire树节点的子节点
		int id;                    //每个病毒的最后一个节点，为病毒id
		Node()
		{
			fail=NULL;
			id=-1;
			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 AC_Automation::GetMatchingCount(char* str)
{
	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)    //这里不做限制，因为任何情况都要匹配到
		{
			if(temp->id>=0) coun[temp->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;
}

void OutPut(int n)
{
	int i;

	for(i=0;i<n;i++)
		if(coun[i])
			cout<<a[i]<<": "<<coun[i]<<endl;

}

int main()
{
	int N,i;

	while(cin>>N)
	{
		AC_Automation ac_tuto;
    	for(i=0;i<N;i++)
		{
     		cin>>a[i];
    		ac_tuto.AddWord(a[i],i);
		}
    	ac_tuto.Build_AC_Automation();
  
		memset(coun,0,sizeof(coun));
		cin>>b;
		ac_tuto.GetMatchingCount(b);
		OutPut(N);
	}
	return 0;
}