当前位置:编程学习 > C/C++ >>

hdu 2222 AC自动机

/*

一道AC自动机模板题,超时次数20+,改了半天终于AC了,代码中标记了从TLE到AC过程修改的关键一步,看样子应该是数组作为函数参数传递时的细节问题,不过还是不明白,如有那位大神明白个中缘由,还望不吝赐教!!!

问题终于解决了,原来是在循环中重复调用 strlen( ) 函数导致了TLE,多谢各位热心朋友的帮助!

注意:若要遍历一个字符数组 str 时要先用一个变量记下 strlen(str) 的值,避免在循环中不停地调用 strlen( )

*/

题目大意:先给出一些单词,然后给出一片文章,统计文章中出现的单词数,这里的每个单词只统计一次。

 

[cpp]
#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 ; 

//释放内存  补充:软件开发 , C++ ,

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,