杭电 hdu 1277 全文检索

第二次

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

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1277
    Name  : hdu  1277 ( 全文检索 )

    Date  : Friday, August 19, 2011
    Time Stage : Many hours

    Result:
4450219	2011-08-19 14:53:51 Accepted 1277 109MS	19256K	4903 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 60006
#define LESSMAX	10009

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

#define root stack[0]

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

char model[MAXSIZE], pattn[LESSMAX] ;
int m, n, num ;
int head, tial ;	// for queue
int stkPtr ;		// for stack 
int sequence[LESSMAX] ; // 按顺序记录能匹配的关键字序号
int iseq ;			// for sequence

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

	tmp = root ;

	for (i = 0 ; i < len ; ++i)
	{
		j = pattn[i] - '0' ;
		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 ;
	head = tial = 0 ;

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

	while (head < tial)
	{
		parntNode = queue[head++] ;
		for (i = 0 ; i < 10 ; ++i)
		{
			if (childNode = parntNode->child[i])
			{
				tmpFail = parntNode->fail ;		// 儿子的错误要从老子身上去总结
				while (tmpFail && !tmpFail->child[i])
					tmpFail = tmpFail->fail ;
				if (tmpFail)	// 找到了某位祖宗跟自己同名同姓的孩子
					childNode->fail = tmpFail->child[i] ;	// 自己失败了就让他接着干吧
				else			// 找到了人类的始祖----猴子了……
					childNode->fail = root ;
				queue[tial++] = childNode ;
			}
		}
	}
}

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

	tmp = root ;
	for (i = 0 ; i < len ; ++i)
	{
		j = model[i] - '0' ;

		// 一开始的时候，用了(!tmp->child[j] && tmp) 来判断，结果只要字符失配，就出现内存访问
		// 错误，因为当tmp不断向根部回溯的时候，当tmp = root ，并且tmp->child[j] == 0 的时候，
		// 下一句便是tmp = tmp->fail，使得tmp 指向根部的失败指针，也就是tmp = 0 ;
		// 然后再判断tmp->child[j] 的时候，就出现内存访问错误了。
		// 于是后来改成了(tmp && !tmp->child[j])，嗯，这一句是没错了，但下一句却错了。
		// tmp = (tmp->child[j]) ? tmp->child[j] : root ; 这一句也出现了上面的问题

		// 我很郁闷，感觉也没有什么问题啊，无奈回头看了看以前的代码，发现原来是：
		// (tmp != root && !tmp->child[j]) 
		// 这有什么不同呢？也就是说，当失败指针使tmp 指向根部时，便不再判断根部的孩子中是否
		// 有匹配项了。于是有人便会问：那不就漏了一次查找了么？

		// 不在while循环里判断，是因为下面的一句可以判断：
		// tmp = (tmp->child[j]) ? tmp->child[j] : root ;
		// 在这里判断根部的孩子也没有匹配项之后，tmp 就正式指向根部，准备从头开始对model 中下
		// 一个字符进行匹配了

		// 当然了，其实这样也是可以的：while (tmp && !tmp->child[j])，不过后面的代码便不得不
		// 有点啰嗦了，一段啰嗦的代码，显然不是程序员所追求的……起码现在如此≈≈≈⌒_⌒

		while (tmp != root && !tmp->child[j])	// 向源头方向寻找匹配项，或者统统失配，换下一个字符
			tmp = tmp->fail ;
		tmp = (tmp->child[j]) ? tmp->child[j] : root ;	// 如果统统失配，当然要从根部重新开始了

		tmpFail = tmp ;	// 给tmp弄个分身，艰苦的“人口普查”工作就交给他了……
		while (tmpFail->cnt)
		{
			sequence[iseq++] = tmpFail->num ;
			tmpFail->cnt = 0 ;
			tmpFail = tmpFail->fail ;
		}
	}
}

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

int main ()
{
	int i ;
	int len ;
	while (scanf ("%d%d", &m, &n) != EOF)
	{
		len = 0 ;
		iseq = 0 ;

		scanf ("%s", model) ;
		getchar () ;
		len = strlen (model) ;
		for (i = 1 ; i < m ; ++i)
		{
			scanf ("%s", model + len * i) ;
			getchar () ;
		}
		getchar () ;

		stkPtr		= 1 ;
		stack[0]	= (NODE *) calloc (1, sizeof (NODE)) ;

		for (i = 0 ; i < n ; ++i)
		{
			scanf ("[Key No. %d] %s", &num, pattn) ;
//			printf ("%s\n", pattn) ;
			getchar () ;
			makeTrie () ;
		}
		makeFail () ;
		ACAutomation () ;

		if (iseq)
		{
			printf ("Found key:") ;
			for (i = 0 ; i < iseq ; ++i)
				printf (" [Key No. %d]", sequence[i]) ;
			puts ("") ;
		}
		else
			puts ("No key can be found !") ;

		recycle () ;
	}
	return 0 ;
}

第一次

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

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1277
    Name  : hdu  1277 ( 全文检索 )

    Date  : Friday, June 24, 2011
    Time Stage : Many days

    Result:
4088782	2011-06-24 22:10:34	Accepted	1277
125MS	19304K	4346 B
C++	pyy

4088768	2011-06-24 22:05:15 Wrong Answer 1277 0MS 240K 4218 B C++ pyy


Test Data:

Review:
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SZ_MODEL    60001
#define SZ_PATN     66
#define NUM_PATN    10001
#define NUM_ELEM    10

#define FIRST_ELEM  ('0')

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

NODE *trie[NUM_PATN * SZ_PATN], *queue[NUM_PATN * SZ_PATN], *p, *root ;

char amodel[SZ_MODEL], apattern[SZ_PATN] ;
int line, keyword, len, num, count, cursor, find ;

// 两个数组是必须的，一个用来记录先后顺序，一个用来判断是否已经出现过
int indices[NUM_PATN], repeat[NUM_PATN] ;

void initialization ()
{
    len = 0 ;
    cursor = 0 ;
    find = 0 ;
    trie[cursor++] = (NODE *) calloc (1, sizeof (NODE)) ;
    memset (repeat, 0, sizeof (repeat)) ;
    root = *trie ;
}

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

void makeTrie ()
{
    char *s = apattern ;
    int index ;
    
    p = root ;
    
    while (*s)
    {
        index = *s++ - FIRST_ELEM ;
//        printf ("%d ", index) ;
        if (! (p->child[index]))
        {
            trie[cursor] = (NODE *) calloc (1, sizeof (NODE)) ;
            memset (trie[cursor], 0, sizeof (trie[cursor])) ; //-----------------------------
            p->child[index] = trie[cursor++] ;
        }
        p = p->child[index] ;
    }
    ++p->cnt ;	// 多余的变量
    p->id = num ;
}

void makeFail ()
{
    int head, tial, i ;
    NODE *tmpFail ;
    
    head = tial = 0 ;   // initialize index
    
    root->fail = 0 ;
    
    for (i = 0 ; i < NUM_ELEM ; ++i)
    {
        if (root->child[i])
        {
            root->child[i]->fail = root ;
            queue[tial++] = root->child[i] ;
        }
    }
    
    while (head != tial)
    {
        p = queue[head++] ;
        for (i = 0 ; i < NUM_ELEM ; ++i)
        {
            if (p->child[i])
            {
                queue[tial++] = p->child[i] ;   // enqueue
                
                //-------------- make failure pointer-----------------------
                tmpFail = p->fail ;
                while (tmpFail)
                {
                    if (tmpFail->child[i])
                    {
                        p->child[i]->fail = tmpFail->child[i] ;
                        break ;
                    }
                    tmpFail = tmpFail->fail ;
                }
                
                if (!tmpFail)
                    p->child[i]->fail = root ;
            }
        }
    }
}

void acAutomation ()
{
    NODE *tmp ;
    char *s = amodel ;
    int index ;
    
    p = root ;
    
    while (*s)
    {
        index = *s++ - FIRST_ELEM ;

        while (p->child[index] == NULL && p != root)
            p = p->fail ;
        
		/* 此处切忌使用 p = (p == root) ? p : p->child[index] ; 这样的语句。
		   p 的下一个值不能通过 是否与 root 相等来判断
		 */
        p = (p->child[index] == NULL) ? p : p->child[index] ;
        
        tmp = p ;
        
        while (tmp->id)
        {
            if (!repeat[tmp->id])
            {
                indices[find++] = tmp->id ;
                repeat[tmp->id] = 1 ;
            }

            tmp->id = 0 ;
            tmp = tmp->fail ;
        }
    }
}

int main ()
{
    int i ;
    char c ;
    
//    freopen ("test.txt", "r", stdin) ;

    while (scanf ("%d%d", &line, &keyword) != EOF)
    {
        initialization () ;
        
        while (line--)
        {
            scanf ("%s%c", amodel + len, &c) ;	
			// %c 和 c 是读取 '\n'用的，
			// 不能这样写 ： scanf ("%s\n", amodel + len) ; 下同
            len = strlen (amodel) ;
        }
        
        getchar () ;	// 注意吸收掉一个空行
        
        while (keyword--)
        {
            scanf ("[Key No. %d] %s%c", &num, apattern, &c) ;
            makeTrie () ;
        }
        makeFail () ;
        
        acAutomation () ;
        
        if (find)
        {
            printf ("Found key:") ;
            for (i = 0 ; i < find ; ++i)
                printf (" [Key No. %d]", indices[i]) ;
            puts ("") ;
        }
        else
            puts ("No key can be found !") ;
            
        recycle () ;
    }

    return 0 ;
}