杭电 HDU 2222 Keywords Search

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

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2222
	Name  : 2222 Keywords Search

	Date  : Tuesday, 18 August, 2011
	Time Stage : Many hours .....

	Result:
4445107	2011-08-18 19:53:24 Accepted 2222 234MS	30152K 3051 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 infinity    0x7f7f7f7f
#define minus_inf    0x80808080

#define MAXSIZE 1000009
#define LESSMAX	55

typedef struct tagNODE {
//	int fail ;
	int cnt ;
	struct tagNODE * child[26], * fail ;
} NODE ;

char model[MAXSIZE], pattn[LESSMAX] ;

int tcase, n ;
int stkPtr ;		// pointer for stack
int head, tial ;	// pointers for queue
int count ;			// match words count

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

#define root stack[0]

void makeTrie ()
{
	int i, j ;
	int len = strlen (pattn) ;

	tmp = stack[0] ;

	for (i = 0 ; i < len ; ++i)
	{
		j = pattn[i] - 'a' ;
		if (!tmp->child[j])
		{
			newNode			= (NODE *) calloc (1, sizeof (NODE)) ;
			stack[stkPtr++]	= newNode ;								// 注意1
			tmp->child[j]	= newNode ;
		}
		tmp = tmp->child[j] ;
//		printf ("%c: %d, cnt: %d\n", pattn[i], tmp, tmp->cnt) ;
	}
	++tmp->cnt ;
//	printf ("-------.%c, %d\n", pattn[i-1], tmp->cnt) ;
}

void makeFail ()
{
	int i, j ;

	head = tial = 0 ;

	for (i = 0 ; i < 26 ; ++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 < 26 ; ++i)
		{
			childNode = parntNode->child[i] ;
			if (childNode)
			{
				tmp = parntNode->fail ;
				while (tmp && !tmp->child[i])
					tmp = tmp->fail ;
				if (tmp)
					childNode->fail = tmp->child[i] ;
				else
					childNode->fail = root ;

				queue[tial++] = childNode ;
			}
		}
	}
}

void ACAutomation ()
{
	int i, j ;
	int len = strlen (model) ;
	NODE * tmpFail ;

	tmp = root ;

	for (i = 0 ; i < len ; ++i)
	{
		j = model[i] - 'a' ;
		while (!tmp->child[j] && tmp != root)
			tmp = tmp->fail ;
		tmp = (tmp->child[j]) ? tmp->child[j] : tmp ;

		// 在相同递减后缀并且未被匹配过的字符串间跳跃
		// 并且记录cnt 值，然后清空cnt 值，表示以此
		// 字符结尾的这个单词已经记录过了

		// 但要注意，用来跳跃的指针变量，由于要不断地
		// 改变，即通过fail 指针向根寻找，所以要另外
		// 使用一个临时变量，不能直接用tmp 否则在下
		// 一次的for循环就会没用了
		tmpFail = tmp ;	
		while (tmpFail->cnt)
		{
//			printf ("%c\n", model[i]) ;
			count += tmpFail->cnt ;
			tmpFail->cnt = 0 ;
			tmpFail = tmpFail->fail ;
		}
	}
}

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

int main ()
{
	int i, j ;
	while (scanf ("%d", &tcase) != EOF)
	{
		while (tcase--)
		{
			count		= 0 ;
			stkPtr		= 1 ;		// 如果用了0 ，在“注意1”
			// 里stack[0]的值会被覆盖掉，然后不断悲剧……
			stack[0]	= (NODE *) calloc (1, sizeof (NODE)) ;

			scanf ("%d", &n) ;
			for (i = 0 ; i < n ; ++i)
			{
				scanf ("%s", pattn) ;
				getchar () ;
				makeTrie () ;
			}
			scanf ("%s", model) ;		// 这一步经常忘
			makeFail () ;
			ACAutomation () ;
			printf ("%d\n", count) ;

			recycle () ;	// 释放内存
		}
	}
	return 0 ;
}

------------------------------------新旧世纪永恒的分割线---------------------------------------------------

纠结啊～郁闷啊～这题是所谓的 ac自动机 模版题 居然一直爆内存？！！试了我几天几十次啊！！纠结啊。悲剧啊。我对比了下人家的代码，感觉自己的数组明明开得比人家少啊！怎么还是爆了？一开始以为是用了 queue类 的问题，但后来改用静态数组，依旧爆！今天，没有办法了，全部改用 calloc 并且及时释放内存，不开结构体数组了，只开了两个结构体指针数组。好吧，辛辛苦苦，终于提交了……AC了，内牛满面啊～～～老天啊，您老人家终于肯看我一眼了么？

附上大牛的解题报告：

http://www.cppblog.com/mythit/archive/2009/07/30/80633.html
http://www.cnblogs.com/destinydesigner/archive/2009/10/15/1584191.html

http://www.dev-club.net/xiangxixinxi/22010072906013413/201102100439240.html

4075629	2011-06-18 14:40:59	Accepted	2222	203MS	30184K	2807 B	C++	pyy
4069611	2011-06-14 20:10:26	Memory Limit Exceeded	2222	62MS	55052K	2883 B	C++	pyy
4069609	2011-06-14 20:09:48	Memory Limit Exceeded	2222	31MS	33368K	2885 B	G++	pyy
4069607	2011-06-14 20:09:32	Memory Limit Exceeded	2222	62MS	55124K	2927 B	G++	pyy
4069605	2011-06-14 20:06:38	Memory Limit Exceeded	2222	62MS	55052K	2927 B	C++	pyy
4069604	2011-06-14 20:05:47	Compilation Error	2222	0MS	0K	2906 B	C++	pyy
4069602	2011-06-14 20:05:15	Memory Limit Exceeded	2222	62MS	55056K	2925 B	C++	pyy
4069451	2011-06-14 18:19:49	Runtime Error (ACCESS_VIOLATION)	2222	62MS	6728K	2944 B	C++	pyy
4069377	2011-06-14 17:27:08	Wrong Answer	2222	312MS	28464K	2642 B	C++	pyy
4069374	2011-06-14 17:25:54	Memory Limit Exceeded	2222	62MS	55064K	2640 B	C++	pyy
4069373	2011-06-14 17:25:42	Memory Limit Exceeded	2222	62MS	55064K	2640 B	C++	pyy
4069368	2011-06-14 17:23:55	Memory Limit Exceeded	2222	46MS	55056K	2576 B	G++	pyy
4069365	2011-06-14 17:21:47	Memory Limit Exceeded	2222	62MS	55056K	2589 B	G++	pyy
4069364	2011-06-14 17:21:36	Memory Limit Exceeded	2222	62MS	55068K	2589 B	C++	pyy
4069363	2011-06-14 17:20:12	Memory Limit Exceeded	2222	62MS	55068K	2589 B	C++	pyy

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

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2222
	Name  : 2222 Keywords Search

	Date  : Saturday, 18 June, 2011
	Time Stage : Many days .....

	Result:

Test Data:

Review:
//----------------------------------------------------------------------------*/


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

#define SIZE    (50 * 10000 + 1)
#define SIZE_OF_MODEL   1000010

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

NODE *trie[SIZE], *root, *p, *queue[SIZE] ;

char apattern[55], amodel[SIZE_OF_MODEL] ;
int ikeyword, itcase, icount, ihead, itial, icursor ;

void initial ()
{
    icursor = 0 ;
    icount = 0 ;
    root = (NODE*) calloc (1, sizeof (NODE)) ;
}

void recycle ()
{
	while (icursor)
	{
		free (trie[--icursor]) ;
	}
	
	free (root) ;
}

void makeTrie ()
{
    const int ciLen = strlen (apattern) ;
    int i, j, index ;
    p = root ;
    
    for (i = 0 ; i < ciLen ; ++i)
    {
        index = apattern[i] - 'a' ;
        if (! (p->child[index]))
        {
            trie[icursor] = (NODE *) calloc (1, sizeof (NODE)) ;
            p->child[index] = trie[icursor++] ;
        }
        p = p->child[index] ;
    }
    ++ p->cnt ;
}

void makeFail ()
{
	NODE *tmp, *tmpFail ;
	int i, j ;
	ihead = itial = 0 ;
//	root->fail = 0 ;
	
	for (i = 0 ; i < 26 ; ++i)
	{
		if (root->child[i])
		{
			root->child[i]->fail = root ;
			queue[itial++] = root->child[i] ;
		}
	}
	
	while (ihead != itial)
	{
		tmp = queue[ihead++] ;		// dequeue
		for (i = 0 ; i < 26 ; ++i)
		{
			if (tmp->child[i])
			{
				queue[itial++] = tmp->child[i] ;	// enqueue
				tmpFail = tmp->fail ;
				while (tmpFail)
				{
					if (tmpFail->child[i])
					{
						tmp->child[i]->fail = tmpFail->child[i] ;
						break ;
					}
					tmpFail = tmpFail->fail ;
				}
				
				if (!tmpFail)
				{
					tmp->child[i]->fail = root ;
				}
			}
		}
	}
}

void acAutomation ()
{
	const int ciLen = strlen (amodel) ;
	int i, index ;
	NODE *tmp ;
	
	p = root ;
	i = 0 ;
	while (i < ciLen)
	{
		index = amodel[i] - 'a' ;
		while (p->child[index] == NULL && p != root)
			p = p->fail ;

//		printf ("/n1: %d/n", p->cnt) ;
		p = (p->child[index] == NULL) ? p : p->child[index] ;
		
		tmp = p ;
		while (tmp->cnt)
		{
			icount += tmp->cnt ;
			tmp->cnt = 0 ;
			tmp = tmp->fail ;
			
//			printf ("%d/t", icount) ;
		}
		
		++i ;
	}
}

int main ()
{
    int i, j ;
    while (scanf ("%d", &itcase) != EOF)
    {
        while (itcase--)
        {
            initial () ;
            
            scanf ("%d", &ikeyword) ;
            while (ikeyword--)
            {
                scanf ("%s", apattern) ;
                makeTrie () ;
            }
            makeFail () ;
            scanf ("%s", amodel) ;
            
            acAutomation () ;
            
            printf ("%d/n", icount) ;
            
            recycle () ;
        }
    }
    return 0 ;
}