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

说一下这题要注意的地方，因为目标串里面有不是大写字母的字符，所以每次进行匹配的时候要判断一下，如果不是大写字母就continue掉，注意此时要把P指针指向根节点。

其他就没什么了，就是模版AC自动机。

对了，还有就是题目是多组输入。。。。。。WA的少年赶紧去改掉。。目测就能过了。。

更新了删除节点，释放内存，因为做到一道题目不释放内存会MLE，所以把这里前面的代码也加进去，方便以后整理模版。

#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[26] ;  
    int count ;  
    int id ;  
    node() {  
        fail = 0 ;  
        count = 0 ;  
        mem(next , 0) ;  
        id = 0 ;  
    }  
}*qe[5000005] ;  
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] - 'A' ;  
        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 < 26 ; 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] ;  
            }  
        }  
    }  
}  
int anss[1111] ;  
int search(char *a) {  
    int l = strlen(a) ;  
    node *p = root ;  
    int ans = 0 ;  
    for (int i = 0  ; i < l ; i ++ ) {  
        int tt = a[i] - 'A' ;  
        if(tt < 0 || tt >= 26){  
            p = root ;  
            continue ;  
        }  
        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[temp -> id] ++ ;  
            //temp -> count = -1 ;   
            temp = temp -> fail ;  
        }  
    }  
    return ans ;  
}  
char a[1111][55] ;  
char b[2000005] ;  
void deleteAll(node *p){  
    for (int i = 0 ; i < 26 ;i ++ ){  
        if(p -> next[i] != 0){  
            deleteAll(p -> next[i]) ;  
        }  
    }  
    delete p ;  
}  
int main() {  
    int n ;  
    while(cin >> n ) {  
        mem(anss, 0) ;  
        root = new node() ;  
        for (int i = 1 ; i <= n ; i ++ ) {  
            scanf("%s",a[i]) ;  
            insert(a[i] , i) ;  
        }  
        build() ;  
        scanf("%s",b) ;  
        search(b) ;  
        for (int i = 1 ; i <= n ; i ++ ) {  
            if(anss[i]) {  
                cout << a[i] << ": " << anss[i] << endl;  
            }  
        }  
        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[26] ;
    int count ;
    int id ;
    node() {
        fail = 0 ;
        count = 0 ;
        mem(next , 0) ;
        id = 0 ;
    }
}*qe[5000005] ;
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] - 'A' ;
        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 < 26 ; 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] ;
            }
        }
    }
}
int anss[1111] ;
int search(char *a) {
    int l = strlen(a) ;
    node *p = root ;
    int ans = 0 ;
    for (int i = 0  ; i < l ; i ++ ) {
        int tt = a[i] - 'A' ;
        if(tt < 0 || tt >= 26){
            p = root ;
            continue ;
        }
        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[temp -> id] ++ ;
            //temp -> count = -1 ;
            temp = temp -> fail ;
        }
    }
    return ans ;
}
char a[1111][55] ;
char b[2000005] ;
void deleteAll(node *p){
    for (int i = 0 ; i < 26 ;i ++ ){
        if(p -> next[i] != 0){
            delet

HDU 3065 AC自动机 (一)