HDU 2896 AC自动机 - c++编程基础

TOP

HDU 2896 AC自动机 (一)

2014-11-23 22:13:32 【大中小】浏览:2957次

Tags：HDU 2896 动机

中文题，题意就不解释了。

这道题把我坑了下，应该是做题不仔细的原因，一开始我以为是26个字母的（没认真读题，看样例的结果），然后RE了好几发，最多发现题目里的描述是ASCLL码表里面的可见字符，然后将建字典树过程中的0 - 25的循环改成0 - 127 就过了。

讲一下思路，这道题就是AC自动机的模版题，唯一需要注意的就是加一个id的域来存这个字符串的序号，最后输出的时候要按从小到大的顺序，我直接全部扔进set输出了。

不过我感觉数据有点水啊。。。总感觉A的不是很踏实。

加了释放内存，但是发现内存没比原来的少，难道数据只有一组o( )o

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#define PI acos(-1.0)   
#define Max 2505   
#define inf 1<<28   
#define LL(x) ( x << 1 )   
#define RR(x) ( x << 1 | 1 )   
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
#define PII pair   
using namespace std;  
  
  
struct node {  
    node *fail ;  
    node *next[128] ;  
    int count ;  
    int id ;  
    node() {  
        fail = 0 ;  
        count = 0 ;  
        mem(next , 0) ;  
        id = 0 ;  
    }  
}*qe[1000005] ;  
node *root = 0 ;  
//insert a[] .   
void insert(char *a,int id) {  
    node *p = root ;  
    int l = strlen(a) ;  
    for (int i = 0 ; i < l ; i ++ ) {  
        int tt = a[i] ;  
        if(p -> next[tt] == 0) {  
            p -> next[tt] = new node() ;  
        }  
        p = p -> next[tt] ;  
    }  
    p -> count ++ ;  
    p -> id = id ;  
}  
//build *fail .   
void build() {  
    root -> fail = 0 ;  
    int h = 0 , t = 0 ;  
    qe[h ++ ] = root ;  
    while(h > t) {  
        node *temp = qe[t ++ ] ;  
        node *p = 0 ;  
        for (int i = 0 ; i < 128 ; i ++ ) {  
            if(temp -> next[i] != 0) {  
                if(temp == root)temp -> next[i] -> fail = root ;  
                else {  
                    p = temp -> fail ;  
                    while(p != 0) {  
                        if(p -> next[i] != 0) {  
                            temp -> next[i] -> fail = p -> next[i] ;//找到匹配   
                            break ;  
                        }  
                        p = p -> fail ;  
                    }  
                    if(p == 0)temp -> next[i] -> fail = root ;//如果没找到，则将fail指向root   
                }  
                qe[h ++ ] = temp -> next[i] ;  
            }  
        }  
    }  
}  
setanss[1111] ;  
int search(char *a ,int id) {  
    int l = strlen(a) ;  
    node *p = root ;  
    int ans = 0 ;  
    for (int i = 0  ; i < l ; i ++ ) {  
        int tt = a[i] ;  
        while(p -> next[tt] == 0 && p != root)p = p -> fail ;  
        p = p -> next[tt] ;  
        p = (p == 0)   root : p ;  
        node *temp = p ;  
        while(temp != root && temp -> count != 0) {  
            ans += temp -> count ;  
            anss[id].insert(temp -> id) ;  
            //temp -> count = -1 ;   
            temp = temp -> fail ;  
        }  
    }  
    return ans ;  
}  
  
void deleteAll(node *p){  
    for (int i = 0 ; i < 128 ; i ++ )  
    if(p -> next[i] != 0){  
        deleteAll(p -> next[i]) ;  
    }  
    delete p ;  
}  
char a[11111] ;  
int num[1111] ;  
int main() {  
    int n ;  
    cin >> n ;  
    getchar() ;  
    root = new node() ;  
    for (int i = 1 ; i <= n ;i ++ ){  
        gets(a) ;  
        insert(a ,i ) ;  
    }  
    int m ;  
    cin >> m ;  
    getchar() ;  
    build() ;  
    for (int i = 1 ; i <= m ;i ++ ){  
        gets(a) ;  
        num[i] = search(a , i) ;  
    }  
    int cc = 0 ;  
    for (int i = 1 ; i <= m ;i ++ ){  
        if(num[i]){  
            printf("web %d:",i) ;  
            for(set::iterator p = anss[i].begin() ; p != anss[i].end() ; ++ p)  
            cout <<" "<< *p ;  
            cc ++ ;  
            puts("") ;  
        }  
    }  
    printf("total: %d\n",cc) ;  
    deleteAll(root) ;  
    return 0 ;  
}  

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair
using namespace std;


struct node {
    node *fail ;
    node *next[128] ;
    int count ;
    int id ;
    node() {
        fail = 0 ;
        count = 0 ;
        mem(next , 0) ;
        id = 0 ;
    }
}*qe[1000005] ;
node *root = 0 ;
//insert a[] .
void insert(char *a,int id) {
    node *p = root ;
    int l = strlen(a) ;
    for (int i = 0 ; i < l ; i ++ ) {
        int tt = a[i] ;
        if(p -> next[tt] == 0) {
            p -> next[tt] = new node() ;
        }
        p = p -> next[tt] ;
    }
    p -> count ++ ;
    p -> id = id ;
}
//build *fail .
void build() {
    root -> fail = 0 ;
    int h = 0 , t = 0 ;
    qe[h ++ ] = root ;
    while(h > t) {
        node *temp = qe[t ++ ] ;
        node *p = 0 ;
        for (int i = 0 ; i < 128 ; i ++ ) {
            if(temp -> next[i] != 0) {
                if(temp == root)temp -> next[i] -> fail = root ;
                else {
                    p = temp -> fail ;
                    while(p != 0) {
                        if(p -> next[i] != 0) {
                            temp -> next[i] -> fail = p -> next[i] ;//找到匹配
                            break ;
                        }
                        p = p -> fail ;
                    }
                    if(p == 0)temp -> next[i] -> fail = root ;//如果没找到，则将fail指向root
                }
                qe[h ++ ] = temp -> next[i] ;
            }
        }
    }
}
setanss[1111] ;
int search(char *a ,int id) {
    int l = strlen(a) ;
    node *p = root ;
    int ans = 0 ;
    for (int i = 0  ; i < l ; i ++ ) {
        int tt = a[i] ;
        while(p -> next[tt] == 0 && p != root)p = p -> fail ;
        p = p -> next[tt] ;
        p = (p == 0)   root : p ;
        node *temp = p ;
        while(temp != root && temp -> count != 0) {
            ans += temp -> count ;
            anss[id].insert(temp -> id) ;
            //temp -> count = -1 ;
            temp = temp -> fail ;
        }
    }
    return ans ;
}

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：杭电--1997--汉诺塔VII--数学题	下一篇：uva 110 Meta-Loopless Sorts 用..