aho_corasick.hpp¶
把多个非空模式串建成稠密 AC 自动机；字符串直接按字节扫描，可按结束位置枚举匹配，或沿失败链累计各模式次数而不展开全部输出。
Complexity: Time: \(O(L + S \mathrm{sig})\) construction, \(O(n + z)\) matching, \(O(n + S + P)\) counting; \(L\) pattern symbols, \(S\) states, \(P\) patterns, \(z\) matches. Space: \(O(S (\mathrm{sig} + 1) + P)\) storage, \(O(z)\) match or \(O(S + P)\) count workspace.
AC 记录：aho_corasick。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(L + S sig) construction, O(n + z) matching,
/// O(n + S + P) counting; L pattern symbols, S states, P patterns, z matches.
/// Space: O(S (sig + 1) + P) storage, O(z) match or O(S + P) count workspace.
#include <array>
#include <cassert>
#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) {
return add_impl(t, [](int c) { return c; });
}
int add(const std::string &t, char a = 'a') {
return add_impl(t, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
/// @brief Build failure links and total transitions in O(number_of_nodes *
/// sig).
void build() {
assert(!ok);
ok = true;
ord.clear();
ord.reserve(nd.size());
ord.push_back(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;
ord.push_back(v);
}
}
for (int at = 1; at < int(ord.size()); at++) {
int u = ord[at];
const auto &fallback = nd[nd[u].lnk].nxt;
auto children = nd[u].nxt;
nd[u].nxt = fallback;
for (int c = 0; c < sig; c++) {
int v = children[c];
if (v == -1) continue;
nd[u].nxt[c] = v;
int lnk = fallback[c];
nd[v].lnk = lnk;
nd[v].dl = nd[lnk].out.empty() ? nd[lnk].dl : lnk;
ord.push_back(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 Matches ordered by end, then decreasing length, then pattern id.
/// End positions are inclusive. Duplicate patterns retain their own ids.
std::vector<std::pair<int, int>> match(const std::vector<int> &s) const {
return match_impl(s, [](int c) { return c; });
}
std::vector<std::pair<int, int>> match(const std::string &s,
char a = 'a') const {
return match_impl(s, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
/// @brief Count each pattern in O(text + nodes + patterns), without listing.
std::vector<long long> count_matches(const std::vector<int> &s) const {
return count_impl(s, [](int c) { return c; });
}
std::vector<long long> count_matches(const std::string &s,
char a = 'a') const {
return count_impl(s, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
private:
template <class R, class Encode> int add_impl(const R &t, Encode encode) {
assert(!ok);
assert(!t.empty());
int st = 0;
for (auto ch : t) {
int c = encode(ch);
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;
}
template <class R, class Encode>
std::vector<std::pair<int, int>> match_impl(const R &s, Encode encode) 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, encode(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;
}
template <class R, class Encode>
std::vector<long long> count_impl(const R &s, Encode encode) const {
assert(ok);
std::vector<long long> cnt(nd.size());
int st = 0;
for (auto ch : s) {
st = transition(st, encode(ch));
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;
}
};
} // namespace noya
// NOYA_AHO_CORASICK_HPP
#ifndef NOYA_AHO_CORASICK_HPP
#define NOYA_AHO_CORASICK_HPP 1
/// @complexity Time: O(L + S sig) construction, O(n + z) matching,
/// O(n + S + P) counting; L pattern symbols, S states, P patterns, z matches.
/// Space: O(S (sig + 1) + P) storage, O(z) match or O(S + P) count workspace.
#include <array>
#include <cassert>
#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) {
return add_impl(t, [](int c) { return c; });
}
int add(const std::string &t, char a = 'a') {
return add_impl(t, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
/// @brief Build failure links and total transitions in O(number_of_nodes *
/// sig).
void build() {
assert(!ok);
ok = true;
ord.clear();
ord.reserve(nd.size());
ord.push_back(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;
ord.push_back(v);
}
}
for (int at = 1; at < int(ord.size()); at++) {
int u = ord[at];
const auto &fallback = nd[nd[u].lnk].nxt;
auto children = nd[u].nxt;
nd[u].nxt = fallback;
for (int c = 0; c < sig; c++) {
int v = children[c];
if (v == -1) continue;
nd[u].nxt[c] = v;
int lnk = fallback[c];
nd[v].lnk = lnk;
nd[v].dl = nd[lnk].out.empty() ? nd[lnk].dl : lnk;
ord.push_back(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 Matches ordered by end, then decreasing length, then pattern id.
/// End positions are inclusive. Duplicate patterns retain their own ids.
std::vector<std::pair<int, int>> match(const std::vector<int> &s) const {
return match_impl(s, [](int c) { return c; });
}
std::vector<std::pair<int, int>> match(const std::string &s,
char a = 'a') const {
return match_impl(s, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
/// @brief Count each pattern in O(text + nodes + patterns), without listing.
std::vector<long long> count_matches(const std::vector<int> &s) const {
return count_impl(s, [](int c) { return c; });
}
std::vector<long long> count_matches(const std::string &s,
char a = 'a') const {
return count_impl(s, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
private:
template <class R, class Encode> int add_impl(const R &t, Encode encode) {
assert(!ok);
assert(!t.empty());
int st = 0;
for (auto ch : t) {
int c = encode(ch);
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;
}
template <class R, class Encode>
std::vector<std::pair<int, int>> match_impl(const R &s, Encode encode) 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, encode(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;
}
template <class R, class Encode>
std::vector<long long> count_impl(const R &s, Encode encode) const {
assert(ok);
std::vector<long long> cnt(nd.size());
int st = 0;
for (auto ch : s) {
st = transition(st, encode(ch));
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;
}
};
} // namespace noya
#endif // NOYA_AHO_CORASICK_HPP
/// @complexity Time: O(L + S sig) construction, O(n + z) matching,
/// O(n + S + P) counting; L pattern symbols, S states, P patterns, z matches.
/// Space: O(S (sig + 1) + P) storage, O(z) match or O(S + P) count workspace.
#include <array>
#include <cassert>
#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) {
return add_impl(t, [](int c) { return c; });
}
int add(const std::string &t, char a = 'a') {
return add_impl(t, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
/// @brief Build failure links and total transitions in O(number_of_nodes *
/// sig).
void build() {
assert(!ok);
ok = true;
ord.clear();
ord.reserve(nd.size());
ord.push_back(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;
ord.push_back(v);
}
}
for (int at = 1; at < int(ord.size()); at++) {
int u = ord[at];
const auto &fallback = nd[nd[u].lnk].nxt;
auto children = nd[u].nxt;
nd[u].nxt = fallback;
for (int c = 0; c < sig; c++) {
int v = children[c];
if (v == -1) continue;
nd[u].nxt[c] = v;
int lnk = fallback[c];
nd[v].lnk = lnk;
nd[v].dl = nd[lnk].out.empty() ? nd[lnk].dl : lnk;
ord.push_back(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 Matches ordered by end, then decreasing length, then pattern id.
/// End positions are inclusive. Duplicate patterns retain their own ids.
std::vector<std::pair<int, int>> match(const std::vector<int> &s) const {
return match_impl(s, [](int c) { return c; });
}
std::vector<std::pair<int, int>> match(const std::string &s,
char a = 'a') const {
return match_impl(s, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
/// @brief Count each pattern in O(text + nodes + patterns), without listing.
std::vector<long long> count_matches(const std::vector<int> &s) const {
return count_impl(s, [](int c) { return c; });
}
std::vector<long long> count_matches(const std::string &s,
char a = 'a') const {
return count_impl(s, [a](unsigned char c) {
return int(c) - int(static_cast<unsigned char>(a));
});
}
private:
template <class R, class Encode> int add_impl(const R &t, Encode encode) {
assert(!ok);
assert(!t.empty());
int st = 0;
for (auto ch : t) {
int c = encode(ch);
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;
}
template <class R, class Encode>
std::vector<std::pair<int, int>> match_impl(const R &s, Encode encode) 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, encode(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;
}
template <class R, class Encode>
std::vector<long long> count_impl(const R &s, Encode encode) const {
assert(ok);
std::vector<long long> cnt(nd.size());
int st = 0;
for (auto ch : s) {
st = transition(st, encode(ch));
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;
}
};
} // namespace noya
// NOYA_AHO_CORASICK_HPP