hdu 1277 全文检索 ac 自动机

好纠结啊，就是因为一个小小的错误，导致一错再错！一开始是这样写的：

p = (p == root) ? p : p->child[index] ;

我觉得跟另一种写法没什么区别啊！？但是后来想一想，区别还是有的，只不过自己看不太清楚而已～～～

 

发现网上几乎没有此题的解题报告，于是贴出来，大家共勉吧～～～

 

/* 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 


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 ;
}