http://acm.hdu.edu.cn/showproblem.php?pid=2222
/*
一道AC自动机模板题,超时次数20+,改了半天终于AC了,代码中标记了从TLE到AC过程修改的关键一步,看样子应该是数组作为函数参数传递时的细节问题,不过还是不明白,如有那位大神明白个中缘由,还望不吝赐教!!!
问题终于解决了,原来是在循环中重复调用 strlen( ) 函数导致了TLE,多谢各位热心朋友的帮助!
注意:若要遍历一个字符数组 str 时要先用一个变量记下 strlen(str) 的值,避免在循环中不停地调用 strlen( )
*/
题目大意:先给出一些单词,然后给出一片文章,统计文章中出现的单词数,这里的每个单词只统计一次。
#include"iostream"
#include"string"
#include"queue"
using namespace std;
char s[1000001],p[55] ;
//结点结构
struct Node
{
int cnt ;
Node *fail ;
Node *next[26] ;
};
Node *root = new Node ;
//初始化结点
void init(Node *t)
{
memset(t->next,NULL,sizeof(t->next)) ;
t->cnt = 0 ;
t->fail = NULL ;
}
//插入新单词
void insert(char *str)
{
int i=0,k ;
Node *p = root ;
Node *newnode ;
while(str[i]){ //若用 for(i=0;i<strlen(str);i++) 一定先记下 strlen(str) 的值,防止TLE
k = str[i] - 'a' ;
if(p->next[k] == NULL){
newnode = new Node ;
init(newnode) ;
p->next[k] = newnode ;
p = newnode ;
}
else{
p = p->next[k] ;
}
i++;
}
p->cnt ++;
}
//确定fail指针
void makeFail()
{
Node *front ;
queue<Node *>q ;
q.push(root) ;
while(!q.empty()){
front = q.front() ;
q.pop() ;
for(int i = 0;i < 26;i++){
if(front->next[i] != NULL){ //父结点有孩子i,则找孩子i的fail指针
if(front == root)
front->next[i]->fail = root ;//与根结点相连的结点的fail指针都指向根结点
else{
Node *temp = front ;
while(temp->fail != NULL){ //父结点fail指针非空
if(temp->fail->next[i] != NULL){ //父结点fail指针指向的结点有孩子i
front->next[i]->fail = temp->fail->next[i] ;
break ;
}
temp = temp->fail ;//父结点向上转移
}
if(temp->fail == NULL)
front->next[i]->fail = root ;
}
q.push(front->next[i]) ;//找到孩子i的fail指针后将孩子i加入队列
}
}
}
}
//在文章中搜索单词
int search(char *str)
{
Node *p = root ;
Node *temp = NULL ;
int i=0,k,ans = 0 ;
while(str[i]){
k=str[i] - 'a' ;
while(p != root && p->next[k] == NULL){
p = p->fail ;
}
if(p->next[k] != NULL){//p记录当前位置最长的后缀匹配,下次从该支继续匹配
p = p->next[k] ;
temp = p ; //用temp继续找当前位置较短的后缀匹配
while(temp != root && temp->cnt != -1){
ans += temp->cnt ;//注意一定是+=,而不能直接++,因为cnt可能为0
temp->cnt = -1 ;
temp = temp->fail ;
}
}
i++;
}
return ans ;
}
//释放内存
void freedom(Node *p)
{
for(int i = 0;i < 26;i++){
if(p->next[i] != NULL)
freedom(p->next[i]) ;
}
delete p ;
}
int main()
{
int t,k,i,ans ;
scanf("%d",&t) ;
while(t--){
init(root) ;
scanf("%d",&k) ;
getchar();
while(k--){
gets(p) ;
insert(p) ;
}
makeFail() ;
gets(s) ;
ans = search(s) ;
printf("%d\n",ans) ;
for(i = 0;i < 26;i ++){//注意root不能删除
if(root->next[i] != NULL)
freedom(root->next[i]) ;
}
}
delete root ;
return 0 ;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
HDU最全ac代码
一款 HDU OJ 的自动刷题工具,搜索来源可选用 百度搜索 / 必应搜索,支持并行以及串行查找,祝早日刷上航电首页哦~ 使用 Python 编写,执行之前你需要在同目录下创建文件 aclog.txt ,然后粘贴进你目前已经 AC 的...
hdu2000-2014ac代码,虽然只有几道,但都是简单的
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu2101AC代码
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
hdu 一些简单题目 ac代码 大概100道
hdu杭电所有题目按照ac数量排序,python分析
自己做的HDU ACM已经AC的题目
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
这是我自己的AC代码,都是自己做的,有的很容易出错,大家看的时候要仔细点,加油
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门