hdu 3065 바이러스 습격 지속 중

바이러스 침투 지속 중
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2876    Accepted Submission(s): 1056
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
이번 AC 오토 매 틱 BFS 는 다른 사람들 이 많이 쓰 는 거 야.이렇게 두 개의 인 자 를 적 게 저장 하면 좀 편리 해 야 한다.

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

typedef struct
{
    int word,fail;
    int next[26];
}Tree;

char str[1005][55];
char s[2000005];
int up;
Tree tree[1000005];
int ans[1005];
queue <int> q;

void Add(char *str,int k)
{
    int i,j,n,now;
    n=strlen(str);
    now=0;
    for (i=0;i<n;i++)
    {
        if (tree[now].next[str[i]-'A']==-1)
        {
            tree[now].next[str[i]-'A']=up;
            tree[up].word=-1;
            memset(tree[up].next,-1,sizeof(tree[up].next));
            up++;
        }
        now=tree[now].next[str[i]-'A'];
    }
    tree[now].word=k;
}

void BFS()
{
    int i,j,n,tmp,tag,t;
    q.push(0);
    while(!q.empty())
    {
        tag=q.front();
        q.pop();
        for (i=0;i<26;i++)
        {
            if (tree[tag].next[i]==-1) continue;
            t=tree[tag].next[i];
            q.push(t);
            if (tag==0)
            {
                tree[t].fail=0;
                continue;
            }
            tmp=tree[tag].fail;
            while (tree[tmp].next[i]==-1 && tmp!=0)
            {
                tmp=tree[tmp].fail;
            }
            if (tree[tmp].next[i]!=-1)
            {
                tree[t].fail=tree[tmp].next[i];
            }
            else
            {
                tree[t].fail=tmp;
            }
        }
    }
}

void Count(char *str)
{
    int n,i,j,now,tag;
    n=strlen(str);
    now=0;
    for (i=0;i<n;i++)
    {
        if (str[i]>'Z' || str[i]<'A')
        {
            now=0;
            continue;
        }
        while (tree[now].next[str[i]-'A']==-1 && now!=0)
        {
            now=tree[now].fail;
        }
        if (tree[now].next[str[i]-'A']!=-1)
        {
            now=tree[now].next[str[i]-'A'];
        }
        tag=now;
        while(tag!=0)
        {
            if (tree[tag].word!=-1) ans[tree[tag].word]++;
            tag=tree[tag].fail;
        }
    }
}

int main()
{
    int i,j,n;
    char ch;
    while(scanf("%d",&n)!=EOF)
    {
        up=1;
        tree[0].fail=0;
        tree[0].word=-1;
        memset(tree[0].next,-1,sizeof(tree[0].next));
        for (i=0;i<n;i++)
        {
            scanf("%s",str[i]);
            Add(str[i],i);
        }
        BFS();
        ch=getchar();
        gets(s);
        memset(ans,0,sizeof(ans));
        Count(s);
        for (i=0;i<n;i++)
        {
            if (ans[i]==0) continue;
            printf("%s: %d
",str[i],ans[i]);
        }
    }
    return 0;
}