AC自动机 – 模板备份

Implemented by array

/*
AC 自动机 多模式串匹配

HDU 2222 模板题

Fuck HDU,
why always stick on input optimization??
Interestring?

*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

void gi(int &a) {
    char t = getchar();
    a = 0;
    for (; !isdigit(t); t = getchar())
        ;
    for (; isdigit(t); a *= 10, a += t - 48, t = getchar())
        ;
}

void gs(string &s) {
    char t;
    s = "";
    for (t = getchar(); !isprint(t); t = getchar())
        ;
    for (; isprint(t); s += t, t = getchar())
        ;
}

template <size_t alphabet_size = 26>
struct Node {
    int ends;
    Node *child[alphabet_size], *fail;
    Node() {
        ends = 0;
        fail = NULL;
        memset(child, 0, sizeof(Node *) * alphabet_size);
    }

    void insert(const string &s) {
        auto c = this;
        int u;
        for (auto e : s) {
            u = e - 'a';
            if (c->child[u] == NULL) {
                c->child[u] = new Node();
            }
            c = c->child[u];
        }
        c->ends++;
    }

    int search(const string &k) {
        int ans = 0, u;
        Node *p = this, *t;
        for (auto e : k) {
            u = e - 'a';
            while (p->child[u] == NULL && p != this) {
                p = p->fail;
            }  // match failed
            p = p->child[u];
            if (p == NULL) {
                p = this;
            }  // reach the end
            t = p;
            while (t != this && t->ends != -1) {
                ans += t->ends;
                // if next line is commented, find all occurrences, otherwise
                // only match once

                t->ends = -1;
                t = t->fail;
            }  // all substrings
        }
        return ans;
    }

    void build_fail() {
        queue<Node *> q;
        q.push(this);
        Node *t, *p;
        while (!q.empty()) {
            t = q.front();
            q.pop();
            p = NULL;
            for (int i = 0; i < alphabet_size; i++) {
                if (t->child[i] != NULL) {
                    // 'this' here must be root
                    if (t == this) {
                        t->child[i]->fail = this;
                    } else {
                        p = t->fail;
                        while (p != NULL) {
                            if (p->child[i] != NULL) {
                                t->child[i]->fail = p->child[i];
                                break;
                            }
                            p = p->fail;
                        }
                        if (p == NULL) {
                            t->child[i]->fail = this;
                        }
                    }
                    q.push(t->child[i]);
                }
            }
        }
    }
};

void exec() {
    Node<26> root;
    int n;
    gi(n);
    string s;
    while (n--) {
        gs(s);
        root.insert(s);
    }
    root.build_fail();
    gs(s);
    cout << root.search(s) << endl;
}

int main() {
    int n = 1;
    // cin >> n;
    while (n--) {
        exec();
    }
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.