`

杭电 hdu 3065 病毒侵袭持续中

阅读更多
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=3065
	Name  : 3065 病毒侵袭持续中

	Date  : Sunday, August 21, 2011
	Time Stage : one hour and a half

	Result:
4463980	2011-08-21 16:05:47	Accepted	3065
156MS	5900K	3738 B
C++	pyy

4463875	2011-08-21 15:54:25	Wrong Answer	3065
187MS	5900K	3703 B
C++	pyy

4463866	2011-08-21 15:53:38	Wrong Answer	3065
312MS	27400K	3716 B
C++	pyy

4463803	2011-08-21 15:47:02	Runtime Error
(ACCESS_VIOLATION)	3065
46MS	27328K	3716 B
C++	pyy

4463790	2011-08-21 15:45:11	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	8264K	3680 B
C++	pyy

4463772	2011-08-21 15:43:07	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	6288K	3670 B
C++	pyy

4463765	2011-08-21 15:42:21	Runtime Error
(ACCESS_VIOLATION)	3065
0MS	252K	3677 B
C++	pyy

4463755	2011-08-21 15:41:44	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	5840K	3675 B
C++	pyy

4463744	2011-08-21 15:41:03	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	5844K	3673 B
C++	pyy

4463739	2011-08-21 15:40:09	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	5844K	3671 B
C++	pyy

4463734	2011-08-21 15:39:38	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	5836K	3670 B
C++	pyy

4463728	2011-08-21 15:39:01	Runtime Error
(ACCESS_VIOLATION)	3065
31MS	5828K	3668 B
C++	pyy



	Test Data:

	Review:
犯了很多低级的错误,也犯了一些严重的错误……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define SafeAccess(a, b) (0 <= (a) && (a) < n && 0 <= (b) && (b) < n)

#define infinity    0x0f0f0f0f
#define minus_inf    0x80808080

#define MAXSIZE	2000009
#define LESSMAX	55
#define CHARNUM	26

typedef struct tagNODE {
	int cnt, num ;
	struct tagNODE * fail, * child[CHARNUM] ;
} NODE ;

#define root stack[0]

NODE * tmp, * tmpFail, * newNode, * parntNode, * childNode ;
NODE * queue[LESSMAX * 1000], * stack[LESSMAX * 1000] ;

int stkPtr ;		// for stack
int head, tial ;	// for queue

int n ;
int count[1001] ;

char pattn[1001][LESSMAX], model[MAXSIZE] ;

void makeTrie (char * ptn, int num)
{
	int i, j ;
	int len = strlen (ptn) ;

	tmp = root ;
	for (i = 0 ; i < len ; ++i)
	{
		j = ptn[i] - 'A' ;
		if (!tmp->child[j])
		{
			newNode			= (NODE *) calloc (1, sizeof (NODE)) ;
			stack[stkPtr++]	= newNode ;
			tmp->child[j]	= newNode ;
		}
		tmp = tmp->child[j] ;
	}
	tmp->num = num ;
	++tmp->cnt ;
}

void makeFail ()
{
	int i, j ;
	head = tial = 0 ;

	for (i = 0 ; i < CHARNUM ; ++i)
	{
		if (root->child[i])
		{
			root->child[i]->fail = root ;
			queue[tial++] = root->child[i] ;
		}
	}

	while (head < tial)
	{
		parntNode = queue[head++] ;
		for (i = 0 ; i < CHARNUM ; ++i)
		{
			if (childNode = parntNode->child[i])
			{
				tmpFail = parntNode->fail ;
				while (tmpFail != root && !tmpFail->child[i])
					tmpFail = tmpFail->fail ;
				// 上一步没有对root的孩子检查是否与childNode匹配
				// 所以这一步这检查一下,不能这样:
				// (tmp == root) ? root : tmpFail->child[i] ;
				childNode->fail = (tmpFail->child[i]) ? 
					tmpFail->child[i] : root ;

				// 最后一步,不要忘了
				queue[tial++] = childNode ;
			}
		}
	}
}

void ACAutomation ()
{
	int i, j ;
	int len = strlen (model) ;
	memset (count, 0, sizeof (count)) ;

	tmp = root ;
	for (i = 0 ; i < len ; ++i)
	{
		if ('A' <= model[i] && model[i] <= 'Z')
		{
			j = model[i] - 'A' ;
			while (!tmp->child[j] && tmp != root)
				tmp = tmp->fail ;
			// root 的child中有没有可以匹配的项,目前还是不知道的
			// 所以下面还要再判断一下, 如果tmp 的child 能匹配到,
			// 则无论tmp 是什么都可以直接用,否则就要它就是一定
			// 是root。这一句由于有两种实现方法,在不看答案代码
			// 的时候,我曾经错误地写成:
			// (tmp == root) ? root : tmp->child[j] 
			// 实际上,当tmp == root 的时候,tmp->child[j] 可能
			// 是能够匹配的,而错误的语句却仍然把root 赋给了tmp
			tmp = (tmp->child[j]) ? tmp->child[j] : root ;

			tmpFail = tmp ;
			while (tmpFail->cnt)
			{
				++count[tmpFail->num] ;
//				tmpFail->cnt = 0 ;
				tmpFail = tmpFail->fail ;
			}
		}
		else
		{
			/* 这句一定要加,否则当出现这样的数据的时候,便会错误:
-----------------------------------------------------------------------
3
AA
BB
CC
A%AB%BC^&CC

正确输出:
CC: 1

错误输出:
AA: 1
BB: 1
CC: 2
-----------------------------------------------------------------------
			为什么会这样呢?
			因为它会认为A%A是连续的!
			所以当出现非英文大写字符时,便要从根部重新开始匹配了!
			当然,不加这句也可以,前提是CHARNUM 要变成128 个!
			并且要在相应的地方进行修改,这样的话,由于child的数目
			增多了,循环的负担也会相应变大,时间自然有所增加!
			*/
			tmp = root ;
		}
	}
}

void recycle ()
{
	while (stkPtr)
		free (stack[--stkPtr]) ;
}

int main ()
{
	int i, j ;
	while (scanf ("%d", &n) != EOF)
	{
		stkPtr = 1 ;
		stack [0] = (NODE *) calloc (1, sizeof (NODE)) ;
		for (i = 1 ; i <= n ; ++i)
		{
			scanf ("%s", pattn[i]) ;
			getchar () ;
			makeTrie (pattn[i], i) ;
		}
		scanf ("%s", model) ;
		makeFail () ;
		ACAutomation () ;

		for (i = 1 ; i <= n ; ++i)
		{
			if (count[i])
			{
				printf ("%s: %d\n", pattn[i], count[i]) ;
			}
		}
		recycle () ;
	}
	return 0 ;
}

分享到:
评论

相关推荐

    杭电HDU ACM培训课件

    通过学习《杭电HDU ACM培训课件》,初学者不仅可以系统地学习到ACM编程所需的基础知识,还能了解实际竞赛中的策略和技巧,从而提高解决问题的能力。这份资源不仅适合参赛者,也对任何想要提升编程能力和算法理解的人...

    杭电HDU2050题的ac程序

    一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    杭电HDU ACM 1005

    杭电ACM1005题源代码,AC了的程序,无问题……

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    计算机网络复习大纲_杭电hdu借鉴.pdf

    而在对等方式中,每个参与者既是服务请求者也是提供者,如P2P文件共享。 网络分为边缘部分和核心部分。边缘部分由所有连接的主机构成,用于通信和资源共享;核心部分由路由器和网络设备组成,负责数据的交换和连通...

    hdu_ACM.rar_ACM_hdu_hdu acm_hdu_ACM_杭电ACM

    杭电hdu acm资料所用杭电的acm题

    HDU杭电 计算机网络实验报告

    这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    杭电(HDU)ACM题解

    HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字

    acm课件简单数学题(杭电)(HDU)

    在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)中,数学是至关重要的一部分,尤其是在解决杭电(Hangzhou Dianzi University,简称HDU)的题目时。本课件"acm课件简单...

    acm课件搜索(杭电)(HDU)

    总的来说,"acm课件搜索(杭电)(HDU)"这一主题为ACM学习者提供了一个宝贵的资料库,特别是对搜索算法的探讨,有助于参赛者提升在竞赛中的表现。通过深入学习和实践,学生能够熟练掌握DFS和BFS,以及其他相关算法...

    HDU 杭电操作系统实验 (通过验收)

    包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...

    杭电(HDU) OJ离线版

    为了方便广大没有网络的朋友.......

Global site tag (gtag.js) - Google Analytics