自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:36:01，当前版本为作者最后更新于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

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