hdu 3065 바이러스 침입 지속 중 (AC 자동 동기)

바이러스 침투 지속 중
                                                                    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
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   。 
    
    
    
    
     
   
   
   
   

 
분석: 이 문 제 는 hdu 2896 과 차이 가 많 지 않 습 니 다. 다만 모든 바이러스 가 발생 하 는 횟수 를 더 출력 했 을 뿐 cnct 배열 로 횟수 를 기록 하면 됩 니 다.

#include<cstdio>
#include<cstring>
using namespace std;

const int kind = 26; //      
const int N = 1005;
const int M = 2000005;
struct node
{
    node *next[kind];
    node *fail;
    int id;//    
    node() {
        for(int i = 0; i < kind; i++)
            next[i] = NULL;
        fail = NULL;
        id = 0;
    }
}*q[51*N];
node *root;
int head, tail;
char source[M], s[M];
char vir[N][55];
int cnt[N];

void Insert(char *str, int id)
{
    node *p = root;
    int i = 0, index;
    while(str[i]) {
        index = str[i] - 'A';
        if(p->next[index] == NULL)
            p->next[index] = new node();
        p = p->next[index];
        i++;
    }
    p->id = id;
}
void build_ac_automation(node *root)
{
    root->fail = NULL;
    q[tail++] = root;
    node *p = NULL;
    while(head < tail) {
        node *temp = q[head++];
        for(int i = 0; i < kind; i++) {
            if(temp->next[i] != NULL) {
                if(temp == root) temp->next[i]->fail = root;
                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 = root;
                }
                q[tail++] = temp->next[i];
            }
        }
    }
}
void Query(char *str)
{
    int i = 0, index;
    node *p = root;
    while(str[i]) {
        index = str[i] - 'A';
        while(p->next[index] == NULL && p != root) p = p->fail;
        p = p->next[index];
        if(p == NULL) p = root;
        node *temp = p;
        while(temp != root && temp->id > 0) {
            cnt[temp->id]++;
            temp = temp->fail;
        }
        i++;
    }
}

int main()
{
    int n;
    while(~scanf("%d",&n)) {
        memset(cnt, 0, sizeof(cnt));
        head = tail = 0;
        root = new node();
      for(int i = 1; i <= n; i++) {
            scanf("%s", vir[i]);
            Insert(vir[i], i);
        }
        build_ac_automation(root);
        scanf("%s",source);
        int len = strlen(source);
        int l = 0;
        for(int i = 0; i <= len; i++) {
            if(source[i] >= 'A' && source[i] <= 'Z') //           ，                  
                s[l++] = source[i];
            else {
                s[l] = '\0';
                Query(s);
                l = 0;
            }
        }
        for(int i = 1; i <= n; i++)
            if(cnt[i])
                printf("%s: %d
",vir[i], cnt[i]);
    }
    return 0;
}