2896

바이러스 가 엄습 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4441    Accepted Submission(s): 1138
Problem Description
태양의 빛 이 점점 달 에 가 려 지면 세상 은 빛 을 잃 고 대 지 는 가장 어두 운 순간 을 맞이 합 니 다...이런 순간 에 사람들 은 매우 흥분 합 니 다.우 리 는 살 아 있 는 동안 500 년 에 한 번 있 는 세계관 을 볼 수 있 습 니 다.그것 이 얼마나 행복 한 일 입 니까?
그러나 인터넷 에는 항상 그런 사이트 들 이 있 는데 민중 의 호기심 을 빌려 일식 을 소개 한 다 는 명목 으로 바 이러 스 를 마구 퍼 뜨리 기 시작 했다.작은 t 는 불행 하 게 도 피해자 중의 하나 가 되 었 다.작은 t 가 이렇게 화가 나 서 그 는 세계 의 모든 바 이러 스 를 가 진 사 이 트 를 찾아내 기로 결정 했다.물론 불가능 하 다 는 것 은 누구나 다 안다.작은 t 는 이 할 수 없 는 임 무 를 완수 하 겠 다 고 고집 했다.그 는"자손 이 무궁무진 하 다!"라 고 말 했다.어 리 석 은 공 뒤에 사람 이 생 겼 다.
모든 일 은 시작 이 어렵다.작은 t 는 많은 바이러스 의 특징 코드 를 수집 하고 기괴 한 사이트 의 소스 코드 를 수집 했다.그 는 이런 사이트 에서 어떤 바이러스 가 있 는 지,또 어떤 바 이러 스 를 가지 고 있 는 지 알 고 싶 어 한다.그 가 도대체 바 이러 스 를 가 진 사 이 트 를 얼마나 수 집 했 는 지 궁금 하 다.이때 그 는 어떻게 손 을 써 야 할 지 몰 랐 다.그래서 여러분 께 도움 을 청 하고 싶 습 니 다.작은 t 는 또 성질 이 급 하 니까 빨리 해결 할 수록 좋아요.
 
Input
첫 번 째 줄 은 하나의 정수 N(1<=N<=500)으로 바이러스 특징 코드 의 개 수 를 나타 낸다.
다음 N 줄 은 줄 마다 바이러스 특징 코드 를 표시 하고 특징 코드 문자열 의 길 이 는 20-200 사이 입 니 다.
모든 바 이러 스 는 하나의 번호 가 있 는데,이에 따라 1-N 이다.
서로 다른 번호 의 바이러스 특징 코드 는 같 지 않 을 것 이다.
그 다음 줄 에 하나의 정수 M(1<=M>=1000)이 있어 사이트 수 를 나타 낸다.
다음 M 줄 은 줄 마다 하나의 사이트 소스 코드 를 표시 하고 소스 문자열 의 길 이 는 7000-10000 사이 입 니 다.
사이트 마다 하나의 번호 가 있 는데 이에 따라 1-M 이다.
이상 문자열 의 문 자 는 모두 ASCII 코드 에서 볼 수 있 는 문자 입 니 다(리 턴 은 포함 되 지 않 습 니 다).
 
Output
순서대로 다음 과 같은 형식 으로 출력 하고 사이트 번호 에 따라 어 릴 때 부터 큰 수출 을 하 며 바 이러 스 를 가 진 사이트 번호 와 바이러스 번 호 를 포함 하 며 줄 마다 독 을 함유 한 사이트 정 보 를 포함한다.
웹 사이트 번호:바이러스 번호,바이러스 번호...
사칭 후 빈 칸 이 하나 있 는데 바이러스 번 호 는 작은 것 부터 큰 것 까지 배열 되 고 두 바이러스 번호 사 이 는 하나의 빈 칸 으로 분리 되 며 한 사이트 에 바이러스 가 포함 되면 바이러스 수 는 3 개 를 넘 지 않 는 다.
마지막 줄 출력 통계 정 보 는 다음 과 같 습 니 다.
바이러스 사이트 수
사칭 후 빈 칸 이 하나 있다.
 
Sample Input

   
   
   
   

    
    
    
    3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    web 1: 1 2 3
total: 1
   
   
   
   

 
Source
2009 Multi-University Training Contest 10 - Host by NIT
 
Recommend
gaojie
 
#include #include
#include
#include
#include
using namespace std;
struct node{
node * next[128];
node* fail;
int count;
node(){
count = -1;
fail = NULL;
memset(next,NULL,sizeof(next));
}
};
node *root;
char str[220];
char s[10100];
int ans_num;
void insert(char *s,int num){
node *p = root;
int l = strlen(s);
int j;
for(int i = 0;ij = s[i];
if(p->next[j]==NULL)p->next[j] =new node();
p =  p->next[j];
}
p->count = num;
}
void build_fail(){
node *tmp;
queue qe;
qe.push(root);
while(!qe.empty()){
tmp = qe.front();
qe.pop();
for(int i = 0;i<128;i++){
if(tmp->next[i]!=NULL){
if(tmp==root){
tmp->next[i]->fail = root;
}else {
node *p = tmp->fail;
while(p!=NULL){
if(p->next[i]!=NULL){
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(p==NULL)tmp->next[i]->fail = root;
}
qe.push(tmp->next[i]);
}
}
}
}
void solve(int n){
set ans;
node *p = root;
for(int i = 0;s[i];i++){
int j = s[i];
while(p->next[j]==NULL && p!=root)p = p->fail;
p = p->next[j];
if(p==NULL)p = root;
node *tmp = p;
while(tmp!=NULL && tmp->count!=-1){
ans.insert(tmp->count);
tmp = tmp->fail;
}
if(ans.size()==3)break;
}
if(ans.size()!=0){
ans_num++;
printf("web %d:",n);
int a[4];
int num = 0;
for(set::iterator it = ans.begin();it!=ans.end();it++){
a[num++] = *it;
}
for(int m=num-1;m>0;m--){
for(int i = 0;ia[i+1]){
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
}
}
for(int i = 0;iprintf(" %d",a[i]);
printf("");
}
}
int main(){
ans_num = 0;
root = new node();
int n;
scanf("%d",&n);
for(int i = 1;i<=n;++i){
scanf("%s",str);
insert(str,i);
}
build_fail();
int m;
scanf("%d",&m);
for(int i = 0;iscanf("%s",s);
solve(i+1);
}
printf("total: %d",ans_num);
return 0;
}