夏休み-acオートマチック-(C-ウイルス侵襲継続中)

2489 ワード

テーマは複数のデータを言っていないのに、私はデータのグループとしてやりました.
コードを見ても間違っていないようですが、提出するとWAになり、午後になりました.なんてことだ!
問題解を探してこそ、複数のデータであることがわかります.「複数のデータがある」と省略されて騙されないようにしましょう.
/* 
  :   ,  HDU 3065 
  : AC     。 
  : trie  ,      (    )           
value ,        “      ”,        26 
       ,  (       )      +1。
*/ 
#include<iostream>
#include<cstring>
#include<queue>
#include<ctype.h>
using namespace std;
const int MAXM=2000100;//    
const int MAXN=50010;//           
char web[MAXM];//   
char virus[1010][55];//       
int virusN[1010];//           
struct trie
{
	int root,trieN;//            
	int child[MAXN][26],value[MAXN],fail[MAXN];//    ,   ,    
	int NewTrie()//    
	{
		value[trieN]=0;
		memset(child[trieN],-1,sizeof(child[trieN]));
		return trieN++;
	}
	void init()//   
	{
		trieN=0;
		root=NewTrie();
	}
	void Insert(char s[],int k)//  
	{
		int x=root;
		for(int i=0;s[i];i++)
		{
			if(child[x][s[i]-'A']==-1)
			{
				child[x][s[i]-'A']=NewTrie();
			}
			x=child[x][s[i]-'A'];
		}
		value[x]=k;//              
	}
	void Build()//  fail  
	{
		int x;
		queue<int> q;
		fail[root]=root;
		for(int i=0;i<26;i++)
		{
			if(child[root][i]==-1)
			{
				child[root][i]=root;
			}
			else
			{
				fail[child[root][i]]=root;
				q.push(child[root][i]);
			}
		}
		while(!q.empty())
		{
			x=q.front();q.pop();
			for(int i=0;i<26;i++)
			{
				if(child[x][i]==-1)
				{
					child[x][i]=child[fail[x]][i];
				}
				else
				{
					fail[child[x][i]]=child[fail[x]][i];
					q.push(child[x][i]);
				}
			}
		}
	}
	void query(char s[])//    
	{
		int x=root,temp;
		for(int i=0;web[i];i++)
		{
			if(!isupper(web[i]))//         ASCII     , 
			{                   //        ,           
				x=0;            //   ,       web         
				continue;
			}
			x=temp=child[x][s[i]-'A'];
			while(temp!=root)
			{
				if(value[temp])//      
				{
					virusN[value[temp]]++;//    +1
				}
				temp=fail[temp];
			}
		}
	}
}ac;
int main()
{
	int n;
	while(cin>>n)
	{
		ac.init();//   
		memset(virusN,0,sizeof(virusN));
		for(int i=1;i<=n;i++)
		{
			cin>>virus[i];
			ac.Insert(virus[i],i);//  
		}
		ac.Build();//  fail
		getchar();
		cin.getline(web,MAXM);//    ,       
		ac.query(web);//  
		for(int i=1;i<=n;i++)
		{
			if(virusN[i])//   0,          >0
			{
				cout<<virus[i];
				cout<<": "<<virusN[i]<<endl;
			}
		}
	}
	return 0;
}