提供一个$acam$的真算法
对点名串建立$acam$,第一问链并加单点查,第二问单点加链并查,$dfs$序拍扁使用树状数组即可,对于链并,将关键节点按$dfs$序排序,相邻元素$lca$进行单点减即可。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 100010, M = 100010;
int n, m;
map<int, int> tr[N];
int fail[N], trie_idx;
int node[N];
int q[N];
vector<int> v[50010];
int e[M], ne[M], h[N], idx;
int dep[N], sz[N], fa[N], son[N];
int ts, dfn[N], top[N];
struct Fenwick {
int tr[N];
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int v) {
for (; x <= ts; x += lowbit(x))
tr[x] += v;
}
inline void add(int l, int r, int v) {
add(l, v), add(r + 1, -v);
}
inline int ask(int x) {
int res = 0;
for (; x; x -= lowbit(x))
res += tr[x];
return res;
}
inline int ask(int l, int r) {
return ask(r) - ask(l - 1);
}
inline void clear() {
memset(tr, 0, sizeof tr);
}
}t;
void insert(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void dfs1(int u, int father) {
fa[u] = father, dep[u] = dep[father] + 1, sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
dfs1(j, u);
sz[u] += sz[j];
if (son[u] == -1 || sz[j] > sz[son[u]]) son[u] = j;
}
}
void dfs2(int u, int t) {
top[u] = t, dfn[u] = ++ts;
if (~son[u]) dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
int insert() {
int p = 0, l;
cin >> l;
for (int i = 1; i <= l; i++) {
int x;
cin >> x;
if (!tr[p][x]) tr[p][x] = ++trie_idx;
p = tr[p][x];
}
return p;
}
void build() {
int tt = -1, hh = 0;
for (auto& [c, p] : tr[0]) q[++tt] = p;
while (hh <= tt) {
int t = q[hh++];
for (auto& [c, p] : tr[t]) {
int j = fail[t];
while (j && !tr[j].count(c)) j = fail[j];
if (tr[j].count(c)) j = tr[j][c];
fail[p] = j, q[++tt] = p;
}
}
memset(h, -1, sizeof h);
for (int i = 1; i <= trie_idx; i++) insert(fail[i], i);
memset(son, -1, sizeof son);
dfs1(0, 0), dfs2(0, 0);
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int l, x;
cin >> l;
for (int j = 1; j <= l; j++) cin >> x, v[i].push_back(x);
v[i].push_back(-1);
cin >> l;
for (int j = 1; j <= l; j++) cin >> x, v[i].push_back(x);
}
for (int i = 1; i <= m; i++) node[i] = insert();
build();
for (int i = 1; i <= n; i++) {
vector<int> nodes;
int j = 0;
for (auto c : v[i]) {
while (j && !tr[j].count(c)) j = fail[j];
if (tr[j].count(c)) j = tr[j][c];
nodes.push_back(j);
}
sort(nodes.begin(), nodes.end(), [&](int a, int b) {
return dfn[a] < dfn[b];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
for (int j = 0; j < nodes.size(); j++) {
int& u = nodes[j];
t.add(dfn[u], 1);
if (j) {
int p = lca(nodes[j], nodes[j - 1]);
t.add(dfn[p], -1);
}
}
}
for (int i = 1; i <= m; i++) {
int& u = node[i];
cout << t.ask(dfn[u], dfn[u] + sz[u] - 1) << '\n';
}
t.clear();
for (int i = 1; i <= m; i++) {
int& u = node[i];
t.add(dfn[u], dfn[u] + sz[u] - 1, 1);
}
for (int i = 1; i <= n; i++) {
vector<int> nodes;
int j = 0;
for (auto c : v[i]) {
while (j && !tr[j].count(c)) j = fail[j];
if (tr[j].count(c)) j = tr[j][c];
nodes.push_back(j);
}
sort(nodes.begin(), nodes.end(), [&](int a, int b) {
return dfn[a] < dfn[b];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
int res = 0;
for (int j = 0; j < nodes.size(); j++) {
int& u = nodes[j];
res += t.ask(dfn[u]);
if (j) {
int p = lca(nodes[j], nodes[j - 1]);
res -= t.ask(dfn[p]);
}
}
cout << res << ' ';
}
return 0;
}