题解 P2292 【[HNOI2004]L语言】
一扶苏一
2020-05-05 20:57:26
## 【AC 自动机】[HNOI2004]L语言
### Description
给定 $n$ 个模式串 $s$ 和 $m$ 个主串 $t$，对于每一个 $t$，请求出其最长的前缀，满足该前缀是由若干模式串（可以多次使用）首尾拼接而成的。
$1 \leq n \leq 20$，$1 \leq m \leq 50$，$1 \leq |s| \leq 10$，$1 \leq |t| \leq 10^6$。
### Analysis
考虑对模式串建出 AC 自动机，把每个 $t$ 放到自动机上进行匹配，记录其每一位在自动机上匹配的节点。设 $t$ 的长度为 $i$ 的前缀在自动机上匹配的结果为 $u$，如果 $u$ 在 fail 树上存在一个长度为 $k$ 的祖先 $v$，满足 $v$ 是一个终止节点，那么该前缀的长度为 $k$ 的后缀就是一个模式串。
设 $f_i$ 为前缀 $i$ 是否可以拼接而成，转移显然：
$$f_{i} = \operatorname{or} \{f_j\}$$
其中前缀 $i$ 存在长度为 $j - i + 1$ 的后缀。在枚举 $j$ 的时候，只需要枚举到 $i - |s| + 1$ 即可，更小的 $j$ 一定不会是模式串。
这是一个 $O(m|s||t|)$ 的做法，但是不够优秀。
注意到 $s$ 的长度只有 $10$，可以状压到一个 int 中。对于自动机的每一个节点，都可以先预处理出它在 fail 树上的祖先中终止节点有那些长度，状压以后用一个变量来存储。具体转移为：
$$g_u = g_{\operatorname{fa}_u} + (2^{\operatorname{len}_u} \times [\text{u is a end-node}])$$
其中 $len_u$ 表示 $u$ 的长度。当 $u$ 为终止节点时，$[\text{u is a end-node}]$ 的值为 $1$，否则为 $0$。
预处理结束后，把主串放在 AC 自动机上跑，同样可以用一个变量 $x$ 记录主串该位置之前 $10$ 个位置中，有哪些长度的 $f$ 值为 true（这里指的是，如果 $f_{i - j} = true$，那么 $x$ 的第 $j$ 位为 true），设当前匹配到了节点 $u$，如果 $g_u$ 与 $x$ 的按位与存在 $1$，那么 $f_i$ 为 true，否则为 false。
这样的转移是 $O(1)$ 的。一共有 $O(|t|)$ 个状态，因此每个主串的复杂度为 $O(|t|)$。
预处理 AC 自动机的复杂度为 $O(n|s||\Sigma|)$，其中 $\Sigma$ 表示字符集。
综上，总复杂度为 $O(n|s||\Sigma|)-O(m|t|)$，是一个单次询问线性的做法。
### Code
```cpp
namespace Fusu {
const int maxt = 26;
const int maxn = 2000005;
void Init();
void Build();
void Solve();
void Main() {
Init();
Build();
Solve();
}
int n, q;
int len[maxn];
char s[maxn];
struct Node {
bool isend;
unsigned mch, depth;
Node *fail;
Node *trans[maxt];
Node() : isend(false), mch(0), depth(0), fail(nullptr) {
memset(trans, 0, sizeof trans);
}
void calc() {
mch = fail->mch;
if (isend) mch |= 1u << depth;
}
};
Node *rot;
void Init() {
scanf("%d%d", &n, &q);
rot = new Node;
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
len[i] = strlen(s + 1);
auto u = rot;
for (int j = 1, x = s[j] - 'a'; j <= len[i]; x = s[++j] - 'a') {
u = u->trans[x] ? u->trans[x] : (u->trans[x] = new Node());
}
u->isend = true;
}
}
std::queue<Node*> Q;
void Build() {
for (auto &u : rot->trans) if (u != nullptr) {
u->fail = rot;
u->depth = 1;
Q.push(u);
} else {
u = rot;
}
for (Node *u, *v; !Q.empty(); Q.pop()) {
u = Q.front();
u->calc();
for (int i = 0; i < maxt; ++i) if ((v = u->trans[i]) != nullptr) {
v->depth = u->depth + 1;
v->fail = u->fail->trans[i];
Q.push(v);
} else {
u->trans[i] = u->fail->trans[i];
}
}
}
void Solve() {
while (q--) {
int ans = 0;
unsigned tmp = 1;
scanf("%s", s + 1);
int m = strlen(s + 1);
auto u = rot;
for (int i = 1, x = s[i] - 'a'; i <= m; x = s[++i] - 'a') {
if (((u = u->trans[x])->mch) & (tmp <<= 1)) {
tmp |= 1;
ans = i;
}
}
qw(ans, '\n');
}
}
} // namespace Fusu
```