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

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

源代码：

#include
#include
#include
using namespace std;

const int KIND=26;
const int MAXLEN=2000005;
const int MAX=1005;

int n,ans,cnt[MAX];
char word[MAX][55],str[MAXLEN];

struct TrieNode
{
	int num;
	TrieNode *fail;
	TrieNode *next[KIND];
	TrieNode()
	{
		num=0;
		fail=NULL;
		memset(next,0,sizeof(next));
	}
};


TrieNode *q[500005];//  


void InsertTrieNode(TrieNode *pRoot,char s[],int number)
{
	TrieNode *p=pRoot;
	int i=0;
	while(s[i])
	{
		int k=s[i]-'A';
		if(p->next[k]==NULL)
			p->next[k]=new TrieNode();
		i++;
		p=p->next[k];
	}
	p->num=number;
}

void Build_AC_automation(TrieNode *pRoot)
{
	int head=0,tail=0,i;
	TrieNode *p;
	pRoot->fail=NULL;
	q[tail++]=pRoot;
	while(head!=tail)
	{
		p=q[head++];
		for(i=0;inext[i]!=NULL)
			{
				if(p==pRoot)
				    p->next[i]->fail=pRoot;
				TrieNode *tmp=p->fail;
				while(tmp!=NULL && tmp->next[i]==NULL)
					tmp=tmp->fail;
				if(tmp==NULL) p->next[i]->fail=pRoot;
				else
				    p->next[i]->fail=tmp->next[i]; 
				q[tail++]=p->next[i];
			}
	}
}

void Search(TrieNode *pRoot,char s[])
{
	int i,res=0;
	memset(cnt,0,sizeof(cnt));
	TrieNode *p,*tmp;
	p=pRoot;
	i=0;
	while(s[i])
	{
		if(s[i]>='A' && s[i]<='Z')
		{
		    int k=s[i++]-'A';
		    while(p->next[k]==NULL && p!=pRoot)
			      p=p->fail;
		     p=p->next[k];
		     if(p==NULL) p=pRoot;
		     tmp=p;
		     while(tmp!=pRoot)// 
		     {
			     if(tmp->num>0)
				 {
				      cnt[tmp->num]++;
				 }
			     tmp=tmp->fail;
		     }
		}
		else //         ,p    
		{
			i++;
			p=pRoot;
		}
	}
	for(i=1;i<=n;i++)
		if(cnt[i]!=0)
			printf("%s: %d
",word[i],cnt[i]);
}


int main()
{
	int i;
	TrieNode *pRoot=new TrieNode();
	while(scanf("%d",&n)!=EOF)
	{
		memset(pRoot->next,NULL,sizeof(pRoot->next));
		getchar();
		for(i=1;i<=n;i++)
		{
			gets(word[i]);
			InsertTrieNode(pRoot,word[i],i);
		}
		Build_AC_automation(pRoot);
		gets(str);
		Search(pRoot,str);
	}
	system("pause");
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

비슷한 이름의 Attribute를 많이 만들어 삭제하는 Houdini

사용 소프트웨어는 Houdini16.5입니다 배열에서는 애트리뷰트의 보간이 잘 동작하지 않는 것과 AttributeCreateSOP 노드에서 Size가 4를 넘는 애트리뷰트를 작성해도 값이 조작할 수 없어 의미가 없...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

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

좋은 웹페이지 즐겨찾기