HDU 2222 Keywords Search

[AC 自動機]

/OwO/就是要用nullptr

#include<queue>
#include<cstdio>
using namespace std;
#define nullptr (node*) nptr
void* nptr;
class node{
public:
    node(){
        for(int lx = 0;lx < 27;lx++)
            child[lx] = nullptr;
        failed = nullptr;
        n = 0;
        reset();
        return;
    }
    ~node(){
        for(int lx = 0;lx < 27;lx++)
            if(child[lx] != nullptr)
                delete child[lx];
        return;
    }
    void reset(){
        counted = false;
        return;
    }
    node* child[27];
    node* failed;
    int n;
    bool counted;
};
class actrie{
public:
    actrie(){ root = new node;}
    void insert(const char* inp){
        node* prc = root;
        for(int lx = 0;inp[lx];lx++){
            int ch = inp[lx] - 'a';
            if(prc->child[ch] == nullptr){
                prc->child[ch] = new node;
            }
            prc = prc->child[ch];
        }
        prc->n++;
        return;
    }
    void make(){
        queue<node*> que;
        root->failed = nullptr;
        root->counted = true;
        que.push(root);
        while(que.size()){
            node* prc = que.front(); que.pop();
            for(int lx = 0;lx < 26;lx++){
                if(prc->child[lx] == nullptr) continue;
                node* nn = prc->failed;
                while(nn != nullptr and nn->child[lx] == nullptr){
                    nn = nn->failed;
                }
                if(nn != nullptr)
                    nn = nn->child[lx];
                if(nn == nullptr)
                    nn = root;
                prc->child[lx]->failed = nn;
                que.push(prc->child[lx]);
            }
        }
        return;
    }
    int query(const char* inp)const{
        int cnt = 0;
        node* ptr = root;
        for(int lx = 0;inp[lx];lx++){
            int ind = inp[lx]-'a';
            while(ptr->child[ind] == nullptr and ptr != root)
                ptr = ptr->failed;
            ptr = ptr->child[ind];
            if(ptr == nullptr) ptr = root;
            node* prc = ptr;
            while(not prc->counted){
                cnt += prc->n;
                prc->counted = true;
                prc->n = -1; //
                prc = prc->failed;
            }
        }
        return cnt;
    }
    ~actrie(){delete root;}
private:
    node* root;
};
char dest[1000005];
int main(){
int T;scanf("%d", &T);while(T--){
    int n;scanf("%d", &n);
    actrie ac;
    for(int lx = 0;lx < n;lx++){
        char inp[55];scanf("%s", inp);
        ac.insert(inp);
    }
    ac.make();
    scanf("%s", dest);
    printf("%d\n", ac.query(dest));
}return 0;}