夏休み-acオートマチック-(C-ウイルス侵襲継続中)
2489 ワード
テーマは複数のデータを言っていないのに、私はデータのグループとしてやりました.
コードを見ても間違っていないようですが、提出するとWAになり、午後になりました.なんてことだ!
問題解を探してこそ、複数のデータであることがわかります.「複数のデータがある」と省略されて騙されないようにしましょう.
コードを見ても間違っていないようですが、提出すると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;
}