hdu 1277 全文检索 ac 自动机
好纠结啊，就是因为一个小小的错误，导致一错再错！一开始是这样写的：p = (p == root) ? p : p-&gt;child ;我觉得跟另一种写法没什么区别啊！？但是后来想一想，区别还是有的，只不过自己看不太清楚而已～～～ 发现网上几乎没有此题的解题报告，于是贴出来，大家共勉吧～～～ /* THE PROGRAM IS MADE BY PYY *//*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1277 Name: hdu1277 ( 全文检索 ) 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 ;} NODE ;NODE *trie, *queue, *p, *root ;char amodel, apattern ;int line, keyword, len, num, count, cursor, find ;// 两个数组是必须的，一个用来记录先后顺序，一个用来判断是否已经出现过int indices, repeat ;void initialization (){ len = 0 ; cursor = 0 ; find = 0 ; trie = (NODE *) calloc (1, sizeof (NODE)) ; memset (repeat, 0, sizeof (repeat)) ; root = *trie ;}void recycle (){ while (cursor--) { free (trie) ; }}void makeTrie (){ char *s = apattern ; int index ; p = root ; while (*s) { index = *s++ - FIRST_ELEM ;// printf ("%d ", index) ; if (! (p->child)) { trie = (NODE *) calloc (1, sizeof (NODE)) ; memset (trie, 0, sizeof (trie)) ; //----------------------------- p->child = trie ; } p = p->child ; } ++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) { root->child->fail = root ; queue = root->child ; } } while (head != tial) { p = queue ; for (i = 0 ; i < NUM_ELEM ; ++i) { if (p->child) { queue = p->child ; // enqueue //-------------- make failure pointer----------------------- tmpFail = p->fail ; while (tmpFail) { if (tmpFail->child) { p->child->fail = tmpFail->child ; break ; } tmpFail = tmpFail->fail ; } if (!tmpFail) p->child->fail = root ; } } }}void acAutomation (){ NODE *tmp ; char *s = amodel ; int index ; p = root ; while (*s) { index = *s++ - FIRST_ELEM ; while (p->child == NULL && p != root) p = p->fail ; /* 此处切忌使用 p = (p == root) ? p : p->child ; 这样的语句。 p 的下一个值不能通过 是否与 root 相等来判断 */ p = (p->child == NULL) ? p : p->child ; tmp = p ; while (tmp->id) { if (!repeat) { indices = tmp->id ; repeat = 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 (" %s%c", &num, apattern, &c) ; makeTrie () ; } makeFail () ; acAutomation () ; if (find) { printf ("Found key:") ; for (i = 0 ; i < find ; ++i) printf (" ", indices) ; puts ("") ; } else puts ("No key can be found !") ; recycle () ; } return 0 ;}
页:
[1]