AC 自动机
定义 \(|s_i|\) 是模板串的长度，\(|S|\) 是文本串的长度，\(|\Sigma|\) 是字符集的大小（常数，一般为 \(26\)），时间复杂度为 \(\mathcal O(\sum|s_i|+|S|)\) 。
// Trie+Kmp，多模式串匹配
struct ACAutomaton {static constexpr int N = 1e6 + 10;int ch[N][26], fail[N], cntNodes;int cnt[N];ACAutomaton() {cntNodes = 1;}void insert(string s) {int u = 1;for (auto c : s) {int &v = ch[u][c - 'a'];if (!v) v = ++cntNodes;u = v;}cnt[u]++;}void build() {fill(ch[0], ch[0] + 26, 1);queue<int> q;q.push(1);while (!q.empty()) {int u = q.front();q.pop();for (int i = 0; i < 26; i++) {int &v = ch[u][i];if (!v)v = ch[fail[u]][i];else {fail[v] = ch[fail[u]][i];q.push(v);}}}}LL query(string t) {LL ans = 0;int u = 1;for (auto c : t) {u = ch[u][c - 'a'];for (int v = u; v && ~cnt[v]; v = fail[v]) {ans += cnt[v];cnt[v] = -1;}}return ans;}
};
回文自动机 PAM（回文树）
应用：
- 本质不同的回文串个数：\(idx - 2\) ；
- 回文子串出现次数。
对于一个字符串 \(s\)，它的本质不同回文子串个数最多只有 \(|s|\) 个，那么，构造 \(s\) 的回文树的时间复杂度是 \(\mathcal O(|s|)\) 。
struct PalindromeAutomaton {constexpr static int N = 5e5 + 10;int tr[N][26], fail[N], len[N];int cntNodes, last;int cnt[N];string s;PalindromeAutomaton(string s) {memset(tr, 0, sizeof tr);memset(fail, 0, sizeof fail);len[0] = 0, fail[0] = 1;len[1] = -1, fail[1] = 0;cntNodes = 1;last = 0;this->s = s;}void insert(char c, int i) {int u = get_fail(last, i);if (!tr[u][c - 'a']) {int v = ++cntNodes;fail[v] = tr[get_fail(fail[u], i)][c - 'a'];tr[u][c - 'a'] = v;len[v] = len[u] + 2;cnt[v] = cnt[fail[v]] + 1;}last = tr[u][c - 'a'];}int get_fail(int u, int i) {while (i - len[u] - 1 <= -1 || s[i - len[u] - 1] != s[i]) {u = fail[u];}return u;}
};
后缀自动机 SAM
定义 \(|\Sigma|\) 是字符集的大小，复杂度为 \(\mathcal O(N\log |\Sigma|)\) 。
// 有向无环图
struct SuffixAutomaton {static constexpr int N = 1e6;struct node {int len, link, nxt[26];int siz;} t[N << 1];int cntNodes;SuffixAutomaton() {cntNodes = 1;fill(t[0].nxt, t[0].nxt + 26, 1);t[0].len = -1;}int extend(int p, int c) {if (t[p].nxt[c]) {int q = t[p].nxt[c];if (t[q].len == t[p].len + 1) {return q;}int r = ++cntNodes;t[r].siz = 0;t[r].len = t[p].len + 1;t[r].link = t[q].link;copy(t[q].nxt, t[q].nxt + 26, t[r].nxt);t[q].link = r;while (t[p].nxt[c] == q) {t[p].nxt[c] = r;p = t[p].link;}return r;}int cur = ++cntNodes;t[cur].len = t[p].len + 1;t[cur].siz = 1;while (!t[p].nxt[c]) {t[p].nxt[c] = cur;p = t[p].link;}t[cur].link = extend(p, c);return cur;}
};
子序列自动机
对于给定的长度为 \(n\) 的主串 \(s\) ，以 \(\mathcal O(n)\) 的时间复杂度预处理、\(\mathcal O(m + \log \textrm{size:}s)\) 的复杂度判定长度为 \(m\) 的询问串是否是主串的子序列。
自动离散化、自动类型匹配封装
template<class T> struct SequenceAutomaton {vector<T> alls;vector<vector<int>> ver;SequenceAutomaton(auto in) {for (auto &i : in) {alls.push_back(i);}sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());ver.resize(alls.size() + 1);for (int i = 0; i < in.size(); i++) {ver[get(in[i])].push_back(i + 1);}}bool count(T x) {return binary_search(alls.begin(), alls.end(), x);}int get(T x) {return lower_bound(alls.begin(), alls.end(), x) - alls.begin();}bool contains(auto in) {int at = 0;for (auto &i : in) {if (!count(i)) {return false;}auto j = get(i);auto it = lower_bound(ver[j].begin(), ver[j].end(), at + 1);if (it == ver[j].end()) {return false;}at = *it;}return true;}
};
朴素封装
原时间复杂度中的 \(\textrm{size:}s\) 需要手动设置。类型需要手动设置。
struct SequenceAutomaton {vector<vector<int>> ver;SequenceAutomaton(vector<int> &in, int size) : ver(size + 1) {for (int i = 0; i < in.size(); i++) {ver[in[i]].push_back(i + 1);}}bool contains(vector<int> &in) {int at = 0;for (auto &i : in) {auto it = lower_bound(ver[i].begin(), ver[i].end(), at + 1);if (it == ver[i].end()) {return false;}at = *it;}return true;}
};