/* 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培训课件》,初学者不仅可以系统地学习到ACM编程所需的基础知识,还能了解实际竞赛中的策略和技巧,从而提高解决问题的能力。这份资源不仅适合参赛者,也对任何想要提升编程能力和算法理解的人...
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
计算机网络复习大纲_杭电hdu.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
而在对等方式中,每个参与者既是服务请求者也是提供者,如P2P文件共享。 网络分为边缘部分和核心部分。边缘部分由所有连接的主机构成,用于通信和资源共享;核心部分由路由器和网络设备组成,负责数据的交换和连通...
杭电hdu acm资料所用杭电的acm题
这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)中,数学是至关重要的一部分,尤其是在解决杭电(Hangzhou Dianzi University,简称HDU)的题目时。本课件"acm课件简单...
总的来说,"acm课件搜索(杭电)(HDU)"这一主题为ACM学习者提供了一个宝贵的资料库,特别是对搜索算法的探讨,有助于参赛者提升在竞赛中的表现。通过深入学习和实践,学生能够熟练掌握DFS和BFS,以及其他相关算法...
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
为了方便广大没有网络的朋友.......