HDU 3065 바이러스 침입 지속 중

http://acm.hdu.edu.cn/showproblem.php?pid=3065
바이러스 침투 지속 중
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7533    Accepted Submission(s): 2626
Problem Description
작은 t. 여러분 이 그의 지난 문 제 를 해결 해 주 셔 서 감사합니다.하지만 바이러스 의 습격 은 계속 되 고 있다.작은 t 의 끊 임 없 는 노력 으로 그 는 인터넷 에서 '모든 악의 근원' 을 발견 했다.이것 은 방대 한 바이러스 사이트 이다. 그 는 많은 바 이러 스 를 가지 고 있 지만 이 사이트 에 포 함 된 바 이러 스 는 매우 이상 하 다. 이런 바이러스 의 특징 코드 는 매우 짧 고 '영어 대문자' 만 포함한다.물론 작은 t 는 백성 을 위해 해 를 제거 하고 싶 지만 작은 t 는 준비 되 지 않 은 전쟁 을 하지 않 는 다.지피지기, 백전백승, 작은 t 가 먼저 해 야 할 일 은 이 바이러스 사이트 의 특징 을 아 는 것 이다. 얼마나 다른 바 이러 스 를 포함 하고 있 는 지, 모든 바이러스 가 몇 번 나 타 났 는 지.여러분 이 그 를 좀 더 도와 줄 수 있 습 니까?
 
Input
첫 번 째 줄 은 하나의 정수 N (1 < = N < = 1000) 으로 바이러스 특징 코드 의 개 수 를 나타 낸다.
다음 N 줄 은 줄 마다 바이러스 특징 코드 를 표시 하고 특징 코드 문자열 의 길 이 는 1 - 50 사이 이 며 '영문 대문자' 만 포함 합 니 다.임의의 두 바이러스 특징 코드 는 완전히 같 지 않 을 것 이다.
그 다음 줄 에 서 는 '모든 악의 근원' 사이트 의 원본 코드 를 표시 하고 원본 문자열 의 길 이 는 20000 이내 이다.문자열 의 문 자 는 모두 ASCII 코드 에서 볼 수 있 는 문자 입 니 다 (리 턴 은 포함 되 지 않 습 니 다).
 
Output
다음 형식 으로 줄 마다 바이러스 발생 횟수 를 출력 합 니 다.나타 나 지 않 은 바 이러 스 는 출력 할 필요 가 없다.
바이러스 특징 코드: 출현 횟수
콜론 후 빈 칸 이 있 으 며, 바이러스 특징 코드 의 입력 순서에 따라 출력 합 니 다.
 
Sample Input

     
     
     
     

      
      
      
      3
AA
BB
CC
ooxxCC%dAAAoen....END
     
     
     
     

 
Sample Output

     
     
     
     

      
      
      
      AA: 2
CC: 1

      
      
      
      
 
       
 
        Hint 
       
 Hit：                       。                          。             Sample   。 
      
      
      
      
       
     
     
     
     

 
Source
2009 Multi-University Training Contest 16 - Host by NIT
 
Recommend
lcy
 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#include <stack>
#define maxn 50000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
#define INF 1<<30
const ull inf = 1LL << 61;
const double eps=1e-5;

using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}
struct ACauto
{
	int ch[maxn][26];
	int sz;
	int f[maxn],last[maxn],val[maxn],cnt[maxn];
	void init()
	{
		sz=1;
		memset(ch[0],0,sizeof ch[0]);
		memset(cnt,0,sizeof cnt);
	}
	int idx(char c)
	{
		if(c<='Z'&&c>='A')
		return c-'A';
		return -1;
	}
	void add(char *s,int v)
	{
		int u=0,len=strlen(s);
		for(int i=0;i<len;i++)
		{
			int c=idx(s[i]);
			if(!ch[u][c])
			{
				memset(ch[sz],0,sizeof ch[sz]);
				val[sz]=0;
				ch[u][c]=sz++;
			}
			u=ch[u][c];
		}
		val[u]=v;
	}
	void getfail()
	{
		queue<int>q;
		f[0]=0;
		for(int c=0;c<26;c++)
		{
			int u=ch[0][c];
			if(u)
			{
				f[u]=0;
				q.push(u);
				last[u]=0;
			}
		}
		while(!q.empty())
		{
			int r=q.front();q.pop();
			for(int c=0;c<26;c++)
			{
				int u=ch[r][c];
				if(!u)
				{
					ch[r][c]=ch[f[r]][c];
					continue;
				}
				q.push(u);
				f[u]=ch[f[r]][c];
				last[u]=val[f[u]]?f[u]:last[f[u]];
			}
		}
	}
	void print(int j)
	{
		if(j)
		{
			cnt[val[j]]++;
			print(last[j]);
		}
	}
	void Find(char *T)
	{
		int n=strlen(T);
		int j=0;
		for(int i=0;i<n;i++)
		{
			int c=idx(T[i]);
			if(c<0){j=0;continue;}
			while(j&&!ch[j][c])j=f[j];
			j=ch[j][c];
			if(val[j])print(j);
			else if(last[j])print(last[j]);
		}
	}
}ac;
char t[2000000];
struct node
{
	char s[55];
}k[1005];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int n;
    while(scanf("%d",&n)!=EOF)
	{
		ac.init();
		for(int i=1;i<=n;i++)
		{
			scanf("%s",k[i].s);
			ac.add(k[i].s,i);
		}
		getchar();
		ac.getfail();
		gets(t);
		ac.Find(t);
		for(int i=1;i<=n;i++)
		{
			if(ac.cnt[i]>0)
			{
				printf("%s: %d
",k[i].s,ac.cnt[i]);
			}
		}

	}
    return 0;
}