aho_corasick.hpp¶
把多个模式串建成自动机，一次扫描文本即可找出所有模式出现位置或累计匹配贡献。
Complexity: Time: O(S sig) build and O(n + z) matching, for S states and z matches. Space: O(S sig + z).
AC 记录：aho_corasick。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(S sig) build and O(n + z) matching, for S states and z matches.
/// Space: O(S sig + z).
#include <array>
#include <cassert>
#include <queue>
#include <string>
#include <utility>
#include <vector>
namespace noya {
/// @brief Aho-Corasick automaton for an integer alphabet [0, sig).
template <int sig = 26> struct aho_corasick {
struct node {
std::array<int, sig> nxt;
int fa = -1;
int lnk = 0;
int dl = -1;
std::vector<int> out;
node() { nxt.fill(-1); }
};
std::vector<node> nd = {node{}};
std::vector<int> pat;
std::vector<int> ord;
bool ok = false;
/// @brief Add a nonempty pattern and return its pattern id.
int add(const std::vector<int> &t) {
assert(!ok);
assert(!t.empty());
int st = 0;
for (int c : t) {
assert(0 <= c && c < sig);
if (nd[st].nxt[c] == -1) {
nd[st].nxt[c] = int(nd.size());
nd.emplace_back();
nd.back().fa = st;
}
st = nd[st].nxt[c];
}
int id = int(pat.size());
pat.push_back(st);
nd[st].out.push_back(id);
return id;
}
int add(const std::string &t, char a = 'a') {
std::vector<int> x;
x.reserve(t.size());
for (unsigned char c : t) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return add(x);
}
/// @brief Build failure links and total transitions in O(number_of_nodes *
/// sig).
void build() {
assert(!ok);
ok = true;
std::queue<int> q;
ord = {0};
for (int c = 0; c < sig; c++) {
int v = nd[0].nxt[c];
if (v == -1) {
nd[0].nxt[c] = 0;
} else {
nd[v].lnk = 0;
nd[v].dl = -1;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
ord.push_back(u);
for (int c = 0; c < sig; c++) {
int v = nd[u].nxt[c];
if (v == -1) {
nd[u].nxt[c] = nd[nd[u].lnk].nxt[c];
continue;
}
int lnk = nd[nd[u].lnk].nxt[c];
nd[v].lnk = lnk;
nd[v].dl = nd[lnk].out.empty() ? nd[lnk].dl : lnk;
q.push(v);
}
}
}
int transition(int st, int c) const {
assert(ok);
assert(0 <= st && st < int(nd.size()));
assert(0 <= c && c < sig);
return nd[st].nxt[c];
}
/// @brief Enumerate matches as (inclusive end position, pattern id).
std::vector<std::pair<int, int>> match(const std::vector<int> &s) const {
assert(ok);
std::vector<std::pair<int, int>> res;
int st = 0;
for (int i = 0; i < int(s.size()); i++) {
st = transition(st, s[i]);
for (int u = st; u != -1; u = nd[u].dl) {
for (int pid : nd[u].out) {
res.emplace_back(i, pid);
}
}
}
return res;
}
std::vector<std::pair<int, int>> match(const std::string &s,
char a = 'a') const {
std::vector<int> x;
x.reserve(s.size());
for (unsigned char c : s) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return match(x);
}
/// @brief Count occurrences of every inserted pattern in O(text + nodes +
/// patterns).
std::vector<long long> count_matches(const std::vector<int> &s) const {
assert(ok);
std::vector<long long> cnt(nd.size());
int st = 0;
for (int c : s) {
st = transition(st, c);
cnt[st]++;
}
for (int i = int(ord.size()) - 1; i > 0; i--) {
int u = ord[i];
cnt[nd[u].lnk] += cnt[u];
}
std::vector<long long> res(pat.size());
for (int id = 0; id < int(pat.size()); id++) {
res[id] = cnt[pat[id]];
}
return res;
}
std::vector<long long> count_matches(const std::string &s,
char a = 'a') const {
std::vector<int> x;
x.reserve(s.size());
for (unsigned char c : s) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return count_matches(x);
}
};
} // namespace noya
#ifndef NOYA_AHO_CORASICK_HPP
#define NOYA_AHO_CORASICK_HPP 1
/// @complexity Time: O(S sig) build and O(n + z) matching, for S states and z matches.
/// Space: O(S sig + z).
#include <array>
#include <cassert>
#include <queue>
#include <string>
#include <utility>
#include <vector>
namespace noya {
/// @brief Aho-Corasick automaton for an integer alphabet [0, sig).
template <int sig = 26> struct aho_corasick {
struct node {
std::array<int, sig> nxt;
int fa = -1;
int lnk = 0;
int dl = -1;
std::vector<int> out;
node() { nxt.fill(-1); }
};
std::vector<node> nd = {node{}};
std::vector<int> pat;
std::vector<int> ord;
bool ok = false;
/// @brief Add a nonempty pattern and return its pattern id.
int add(const std::vector<int> &t) {
assert(!ok);
assert(!t.empty());
int st = 0;
for (int c : t) {
assert(0 <= c && c < sig);
if (nd[st].nxt[c] == -1) {
nd[st].nxt[c] = int(nd.size());
nd.emplace_back();
nd.back().fa = st;
}
st = nd[st].nxt[c];
}
int id = int(pat.size());
pat.push_back(st);
nd[st].out.push_back(id);
return id;
}
int add(const std::string &t, char a = 'a') {
std::vector<int> x;
x.reserve(t.size());
for (unsigned char c : t) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return add(x);
}
/// @brief Build failure links and total transitions in O(number_of_nodes *
/// sig).
void build() {
assert(!ok);
ok = true;
std::queue<int> q;
ord = {0};
for (int c = 0; c < sig; c++) {
int v = nd[0].nxt[c];
if (v == -1) {
nd[0].nxt[c] = 0;
} else {
nd[v].lnk = 0;
nd[v].dl = -1;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
ord.push_back(u);
for (int c = 0; c < sig; c++) {
int v = nd[u].nxt[c];
if (v == -1) {
nd[u].nxt[c] = nd[nd[u].lnk].nxt[c];
continue;
}
int lnk = nd[nd[u].lnk].nxt[c];
nd[v].lnk = lnk;
nd[v].dl = nd[lnk].out.empty() ? nd[lnk].dl : lnk;
q.push(v);
}
}
}
int transition(int st, int c) const {
assert(ok);
assert(0 <= st && st < int(nd.size()));
assert(0 <= c && c < sig);
return nd[st].nxt[c];
}
/// @brief Enumerate matches as (inclusive end position, pattern id).
std::vector<std::pair<int, int>> match(const std::vector<int> &s) const {
assert(ok);
std::vector<std::pair<int, int>> res;
int st = 0;
for (int i = 0; i < int(s.size()); i++) {
st = transition(st, s[i]);
for (int u = st; u != -1; u = nd[u].dl) {
for (int pid : nd[u].out) {
res.emplace_back(i, pid);
}
}
}
return res;
}
std::vector<std::pair<int, int>> match(const std::string &s,
char a = 'a') const {
std::vector<int> x;
x.reserve(s.size());
for (unsigned char c : s) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return match(x);
}
/// @brief Count occurrences of every inserted pattern in O(text + nodes +
/// patterns).
std::vector<long long> count_matches(const std::vector<int> &s) const {
assert(ok);
std::vector<long long> cnt(nd.size());
int st = 0;
for (int c : s) {
st = transition(st, c);
cnt[st]++;
}
for (int i = int(ord.size()) - 1; i > 0; i--) {
int u = ord[i];
cnt[nd[u].lnk] += cnt[u];
}
std::vector<long long> res(pat.size());
for (int id = 0; id < int(pat.size()); id++) {
res[id] = cnt[pat[id]];
}
return res;
}
std::vector<long long> count_matches(const std::string &s,
char a = 'a') const {
std::vector<int> x;
x.reserve(s.size());
for (unsigned char c : s) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return count_matches(x);
}
};
} // namespace noya
#endif // NOYA_AHO_CORASICK_HPP
#include <array>
#include <cassert>
#include <queue>
#include <string>
#include <utility>
#include <vector>
/// @complexity Time: O(S sig) build and O(n + z) matching, for S states and z matches.
/// Space: O(S sig + z).
namespace noya {
/// @brief Aho-Corasick automaton for an integer alphabet [0, sig).
template <int sig = 26> struct aho_corasick {
struct node {
std::array<int, sig> nxt;
int fa = -1;
int lnk = 0;
int dl = -1;
std::vector<int> out;
node() { nxt.fill(-1); }
};
std::vector<node> nd = {node{}};
std::vector<int> pat;
std::vector<int> ord;
bool ok = false;
/// @brief Add a nonempty pattern and return its pattern id.
int add(const std::vector<int> &t) {
assert(!ok);
assert(!t.empty());
int st = 0;
for (int c : t) {
assert(0 <= c && c < sig);
if (nd[st].nxt[c] == -1) {
nd[st].nxt[c] = int(nd.size());
nd.emplace_back();
nd.back().fa = st;
}
st = nd[st].nxt[c];
}
int id = int(pat.size());
pat.push_back(st);
nd[st].out.push_back(id);
return id;
}
int add(const std::string &t, char a = 'a') {
std::vector<int> x;
x.reserve(t.size());
for (unsigned char c : t) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return add(x);
}
/// @brief Build failure links and total transitions in O(number_of_nodes *
/// sig).
void build() {
assert(!ok);
ok = true;
std::queue<int> q;
ord = {0};
for (int c = 0; c < sig; c++) {
int v = nd[0].nxt[c];
if (v == -1) {
nd[0].nxt[c] = 0;
} else {
nd[v].lnk = 0;
nd[v].dl = -1;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
ord.push_back(u);
for (int c = 0; c < sig; c++) {
int v = nd[u].nxt[c];
if (v == -1) {
nd[u].nxt[c] = nd[nd[u].lnk].nxt[c];
continue;
}
int lnk = nd[nd[u].lnk].nxt[c];
nd[v].lnk = lnk;
nd[v].dl = nd[lnk].out.empty() ? nd[lnk].dl : lnk;
q.push(v);
}
}
}
int transition(int st, int c) const {
assert(ok);
assert(0 <= st && st < int(nd.size()));
assert(0 <= c && c < sig);
return nd[st].nxt[c];
}
/// @brief Enumerate matches as (inclusive end position, pattern id).
std::vector<std::pair<int, int>> match(const std::vector<int> &s) const {
assert(ok);
std::vector<std::pair<int, int>> res;
int st = 0;
for (int i = 0; i < int(s.size()); i++) {
st = transition(st, s[i]);
for (int u = st; u != -1; u = nd[u].dl) {
for (int pid : nd[u].out) {
res.emplace_back(i, pid);
}
}
}
return res;
}
std::vector<std::pair<int, int>> match(const std::string &s,
char a = 'a') const {
std::vector<int> x;
x.reserve(s.size());
for (unsigned char c : s) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return match(x);
}
/// @brief Count occurrences of every inserted pattern in O(text + nodes +
/// patterns).
std::vector<long long> count_matches(const std::vector<int> &s) const {
assert(ok);
std::vector<long long> cnt(nd.size());
int st = 0;
for (int c : s) {
st = transition(st, c);
cnt[st]++;
}
for (int i = int(ord.size()) - 1; i > 0; i--) {
int u = ord[i];
cnt[nd[u].lnk] += cnt[u];
}
std::vector<long long> res(pat.size());
for (int id = 0; id < int(pat.size()); id++) {
res[id] = cnt[pat[id]];
}
return res;
}
std::vector<long long> count_matches(const std::string &s,
char a = 'a') const {
std::vector<int> x;
x.reserve(s.size());
for (unsigned char c : s) {
x.push_back(int(c) - int(static_cast<unsigned char>(a)));
}
return count_matches(x);
}
};
} // namespace noya