自动搬运

查看原文

来自洛谷，原作者为

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

搬运于2025-08-24 23:16:42，当前版本为作者最后更新于2025-05-24 19:34:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一句话题解：

考虑枚举答案串在 $s$ 里开头的位置 $s_i$。然后把 $s_{i \sim |s|}$ 这个后缀扔到 $t$ 的子序列自动机上做匹配，那么能匹配上的长度就是以该位置开头的最长所求串。

更细致的题解：

考虑枚举 $s$ 的一个子串 $s'$，然后检查 $s'$ 能否成为 $t$ 的子序列。这是一个经典问题，可以使用子序列自动机解决。

具体的，考虑把 $s'$ 的每一位从前向后在 $t$ 上进行匹配。假设 $s'$ 的前 $i$ 位是 $t$ 的前 $j$ 位的子序列，根据贪心的原则，显然 $j$ 越小越好（这样 $s'$ 后面的位置可以匹配更多的字符）。因此假设当前 $s'$ 的前 $i$ 位匹配了 $t$ 的前 $j$ 位，那么 $s'$ 的第 $i + 1$ 位应该匹配 $t_j$ 后面第一个 $s_{i + 1}'$ 出现的位置。

这样我们需要维护出 $t$ 里每个位置的下一个字符是什么，放在代码的 $f$ 数组里，$f$ 就是 $t$ 的子序列自动机。每次只需要把 $s'$ 放在自动机上跑，没有跑出自动机就说明 $s'$ 是 $t$ 的子串。

进一步的，对于 $s$ 的一个后缀 $suf(s)$，它能在 $t$ 的子序列自动机上被接受的最长前缀长度就是这个后缀能匹配上的最长子串。

所以枚举 $s$ 的后缀，对每个后缀都放到子序列自动机上跑一次就行了。时间复杂度 $O(|s|^2 + |\Sigma||t|)$

#include <bits/stdc++.h>

int main() {
  int T;
  for (std::cin >> T; T; --T) {
    std::string s, t;
    std::cin >> s >> t;
    t = " " + t;
    std::vector f(t.size() + 1, std::vector<int>(26, -1));
    for (int i = t.size() - 1; i; --i) {
      f[i - 1] = f[i];
      f[i - 1][t[i] - 'a'] = i;
    }
    std::string ans;
    for (int i = 0; i < s.size(); ++i) {
      int j = i, p = 0;
      while (j < s.size()) {
        int ch = s[j] - 'a';
        if (f[p][ch] == -1) break;
        p = f[p][ch];
        ++j;
      }
      int len = j - i;
      if (len > ans.length()) {
        ans = s.substr(i, len);
      } else if (len == ans.length()) {
        auto cur = s.substr(i, len);
        if (cur < ans) ans = cur;
      }
    }
    std::cout << ans << std::endl;
  }
}