杭电 hdu 3065 病毒侵袭持续中
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://acm.hdu.edu.cn/showproblem.php?pid=3065Name : 3065 病毒侵袭持续中Date : Sunday, August 21, 2011Time Stage : one hour and a halfResult:44639802011-08-21 16:05:47Accepted3065156MS5900K3738 BC++pyy44638752011-08-21 15:54:25Wrong Answer3065187MS5900K3703 BC++pyy44638662011-08-21 15:53:38Wrong Answer3065312MS27400K3716 BC++pyy44638032011-08-21 15:47:02Runtime Error(ACCESS_VIOLATION)306546MS27328K3716 BC++pyy44637902011-08-21 15:45:11Runtime Error(ACCESS_VIOLATION)306531MS8264K3680 BC++pyy44637722011-08-21 15:43:07Runtime Error(ACCESS_VIOLATION)306531MS6288K3670 BC++pyy44637652011-08-21 15:42:21Runtime Error(ACCESS_VIOLATION)30650MS252K3677 BC++pyy44637552011-08-21 15:41:44Runtime Error(ACCESS_VIOLATION)306531MS5840K3675 BC++pyy44637442011-08-21 15:41:03Runtime Error(ACCESS_VIOLATION)306531MS5844K3673 BC++pyy44637392011-08-21 15:40:09Runtime Error(ACCESS_VIOLATION)306531MS5844K3671 BC++pyy44637342011-08-21 15:39:38Runtime Error(ACCESS_VIOLATION)306531MS5836K3670 BC++pyy44637282011-08-21 15:39:01Runtime Error(ACCESS_VIOLATION)306531MS5828K3668 BC++pyyTest 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 MAXSIZE2000009#define LESSMAX55#define CHARNUM26typedef 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 stackint head, tial ;// for queueint 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 赋给了tmptmp = (tmp->child[j]) ? tmp->child[j] : root ;tmpFail = tmp ;while (tmpFail->cnt){++count[tmpFail->num] ;//tmpFail->cnt = 0 ;tmpFail = tmpFail->fail ;}}else{/* 这句一定要加，否则当出现这样的数据的时候，便会错误：-----------------------------------3AABBCCA%AB%BC^&CC正确输出：CC: 1错误输出：AA: 1BB: 1CC: 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 ;}