AC自动机模板

作者：

在

OI笔记, 字符串, 玄学

我在这里卡了一个周了，终于写出来了qwq

当走到一个节点时，一定要沿着失配路径走，一直走到根节点，因为失配路径所经过的节点已定能匹配到！

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年12月3日, 下午7:11
 */
#pra\
gma GCC optimize("O3")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
using int_t = long long int;
using std::string;
using std::cout;
using std::endl;
using std::strlen;
using std::cin;
using std::queue;
using std::vector;
using std::ifstream;
using std::max;

enum MemoryType {
    preAllocation, dynamicAllocation
};

struct Node {
    Node* children[26];
    int_t id = 0;
    Node* fail = nullptr;
    //标明这个节点是如何分配内存的
    MemoryType type = MemoryType::preAllocation;
//当前节点的某个子节点是否在构建失配路径前就已经存在
    bool raw[26];

    inline Node* &getChild(char chr) {
        return children[chr - 'a'];
    }
};
int_t used;
//预分配一块内存，用来加快程序分配内存的速度
char memPool[sizeof (Node)*20000 + 1];
const int_t size = sizeof (memPool) / sizeof (Node);
Node* root = nullptr;
char buff[1000000 + 10];
char patterns[200][100];
int_t result[200];
//获取一个新的Node
Node* nextNewNode() {
    if (used < size) //预分配的内存还有空位的情况下 直接使用定位new在预分配的内存中分一个Node return new(memPool + (used++) * sizeof (Node)) Node; else { //否则就用new在堆里分配内存 Node* x = new Node; memset(x->children, 0, sizeof (x->children));
        memset(x->raw, 1, sizeof (x->raw));
        x->type = MemoryType::dynamicAllocation;
        return x;
    }
}
//将字符串插入到Trie
inline void insert(const char * str, int_t id) {
    int_t length = strlen(str);
    Node* ptr = root;
    for (int_t i = 0; i < length; i++) {
        //    cout << i << endl;
        //    if (i % 10 == 0) cout << i << endl; if (ptr->getChild(str[i]) == nullptr) {
            ptr->getChild(str[i]) = nextNewNode();
        }
        ptr = ptr->getChild(str[i]);
    }
    ptr->id = id;

}
//构建失配路径
inline void buildUpFailPtrs() {
    queue<Node* > qu;
    for (char chr = 'a'; chr <= 'z'; chr++) { //根节点所有子节点的失配路径指向根 if (root->getChild(chr)) {
            root->getChild(chr)->fail = root;
            qu.push(root->getChild(chr));
        }
    }
    while (qu.empty() == false) {
        Node* front = qu.front();
        qu.pop();
        for (char chr = 'a'; chr <= 'z'; chr++) { Node* & chd = front->getChild(chr);
            if (chd == nullptr) {
                //如果一个节点不存在 那么就补上这条路径 可降低匹配函数中的代码量
                chd = front->fail->getChild(chr);
                front->raw[chr - 'a'] = false;
            } else {
                Node* fail = front->fail;
                while (fail && (fail->getChild(chr) == nullptr)) {
                    fail = fail->fail;
                }
                if (fail == nullptr) fail = root;
                chd->fail = fail->getChild(chr);
                if (chd->fail == nullptr) chd->fail = root;
                qu.push(chd);
            }
        }
    }
}

inline void match(char * str) {
    memset(result, 0, sizeof (result));
    int_t length = strlen(str);
    Node* ptr = root;
    for (int_t i = 0; i < length; i++) {
        //  if (i % 10 == 0) cout << i << endl; ptr = ptr->getChild(str[i]);
        //        cout << "moving to " << ptr << " with str " << str[i] << endl; if (ptr == nullptr) { ptr = root; continue; } Node* temp = ptr; //重要！！！一定要沿着当前节点的失配路径已知往回走，因为这些失配路径上的字符串一定匹配到了！！ while (temp) { // if(temp->id==0) break;
            if (temp->id) {
                //    cout << "found " << patterns[temp->id] << " at pos " << i;
                //       cout << "result " << temp->id << " from " << result[temp->id] << " to " << result[temp->id] + 1 << endl; result[temp->id]++;
            }

            temp = temp->fail;
        }

    }

}
//删掉树
void remove(Node* r) {
    if (r == nullptr) return;
    for (char chr = 'a'; chr <= 'z'; chr++) { if (r->raw[chr - 'a'])
            remove(r->getChild(chr));
    }
    //只有某个节点是使用堆分配的内存时才能delete
    //定位new不能用delete
    if (r->type == MemoryType::dynamicAllocation)
        delete r;
}

int main() {
    int_t n;
    while (true) {
        remove(root);
        memset(memPool, 0, sizeof (memPool));
        used = 0;
        cin>>n;
        if (n == 0) break;

        root = nextNewNode();
        for (int_t i = 1; i <= n; i++) { cin >> patterns[i];
            insert(patterns[i], i);
        }
        buildUpFailPtrs();
        cin>>buff;
        match(buff);
        int_t maxTime = 0;
        for (int_t i = 1; i <= n; i++) {
            maxTime = max(maxTime, result[i]);
        }
        cout << maxTime << endl;
        for (int_t i = 1; i <= n; i++) {
            if (result[i] == maxTime) {
                cout << patterns[i] << endl;
            }
        }
    }
    return 0;
}

评论

发表回复取消回复

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章