「2026 牛客多校 1」L. 子串的子串
https://ac.nowcoder.com/acm/contest/133876/L
给出一个长度为 n 的字符串 S 和一个长度为 n 的序列 a_1, \dots, a_n。有 Q 次询问。每次询问给出一个字符串 t:
如果一个区间 [l, r] (1 \leq l \leq r \leq n) 满足 t 是 S[l : r] 的子串,那么称这个区间为好区间。
求所有好区间的区间和的最大值,以及所有好区间的区间和之和(对 998244353 取模)。保证至少存在一个好区间。
数据范围:1 \leq n \leq 10^5,1 \leq q \leq 3\times 10^5,-10^9 \leq a_i\leq 10^9,1 \leq \sum |t| \leq 3\times 10^5。
时空限制:5s / 1024MiB。
Solution
这个问题应该很难通过数据结构在线快速查询,所以才会启发选手想到暴力。
应该是一个比较经典的结论:将询问串 t 去重之后,所有询问串 t 在 S 中的出现次数之和不超过 O(n\sqrt{\sum |t|}) 级别。
因为本质不同的询问串长 |t| 不超过 \mathcal{O}(\sqrt{\sum |t|}) 级别,同一长度的询问串 endpos 各不相同。
对询问串建 AC 自动机(trie 图),每个节点记录一下向上跳 fail 指针遇到的最近询问节点 up。
然后从左到右扫描 S,扫描到右端点 r 时,维护以 r 结尾的最长匹配串对应的状态。然后在当前状态不断地跳 up 指针,去更新(记录)询问串在 S 中的 endpos。
记 T = \sum |t|,时间复杂度 \mathcal{O}(T|\Sigma| + n\sqrt{T}),空间复杂度 \mathcal{O}(T|\Sigma|)。
#include <bits/stdc++.h>
using i64 = long long;
#define debug(a) std::cout << #a << '=' << (a) << ' '
template <class T>
inline void chmin(T &x, const T &y) {
if (x > y) {
x = y;
}
}
template <class T>
inline void chmax(T &x, const T &y) {
if (x < y) {
x = y;
}
}
const i64 inf = 1e18;
const int mod = 998244353;
const int N = 100100, MaxQ = 300100;
int n, Q;
std::string str;
int a[N];
int belong[MaxQ];
i64 sum[N];
int ssum[N];
i64 pre[N], suf[N];
namespace AC {
const int SIZE = 300100;
int nodeCount = 1;
struct node {
int trans[26];
int fail;
int length;
} t[SIZE];
int flag[SIZE];
int up[SIZE];
std::vector<int> son[SIZE];
int lst[SIZE];
i64 ans1[SIZE];
int ans2[SIZE];
void upd(int u, int r) {
int l = r - t[u].length + 1;
int lstl = lst[u];
lst[u] = l;
chmax(ans1[u], sum[r] - sum[l - 1] + suf[r + 1] + pre[l - 1]);
ans2[u] = (ans2[u] + 1ll * (ssum[n] - ssum[r - 1]) * (l - lstl)) % mod;
ans2[u] = (ans2[u] - 1ll * (ssum[l - 1] - (lstl ? ssum[lstl - 1] : 0)) * (n - r + 1)) % mod;
if (ans2[u] < 0) {
ans2[u] += mod;
}
}
int insert(std::string str) {
int p = 1;
for (char ch : str) {
int v = ch - 'a';
if (!t[p].trans[v]) {
int np = ++ nodeCount;
t[p].trans[v] = np;
t[np].length = t[p].length + 1;
ans1[np] = -inf;
}
p = t[p].trans[v];
}
flag[p] = 1;
return p;
}
void build_fail() {
for (int i = 0; i < 26; i ++) {
t[0].trans[i] = 1;
}
t[1].fail = 0;
std::queue<int> q;
q.push(1);
while (q.size()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i ++) {
if (t[u].trans[i]) {
t[t[u].trans[i]].fail = t[t[u].fail].trans[i];
q.push(t[u].trans[i]);
} else {
t[u].trans[i] = t[t[u].fail].trans[i];
}
}
}
}
void dfs_init(int u) {
up[u] = flag[u] ? u : up[t[u].fail];
for (int v : son[u]) {
dfs_init(v);
}
}
void build_tree() {
for (int i = 2; i <= nodeCount; i ++) {
son[t[i].fail].push_back(i);
}
dfs_init(1);
}
void push(int p, int r) {
while (up[p]) {
p = up[p];
upd(p, r);
p = t[p].fail;
}
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> Q;
std::cin >> str, str = " " + str;
for (int i = 1; i <= n; i ++) {
std::cin >> a[i];
}
for (int i = 1; i <= n; i ++) {
sum[i] = sum[i - 1] + a[i];
ssum[i] = (ssum[i - 1] + sum[i]) % mod;
if (ssum[i] < 0) {
ssum[i] += mod;
}
}
for (int i = 1; i <= n; i ++) {
pre[i] = std::max(pre[i - 1] + a[i], 0LL);
}
for (int i = n; i >= 1; i --) {
suf[i] = std::max(suf[i + 1] + a[i], 0LL);
}
for (int i = 1; i <= Q; i ++) {
std::string t;
std::cin >> t;
belong[i] = AC::insert(t);
}
AC::build_fail();
AC::build_tree();
int p = 1;
for (int i = 1; i <= n; i ++) {
p = AC::t[p].trans[str[i] - 'a'];
AC::push(p, i);
}
for (int i = 1; i <= Q; i ++) {
int p = belong[i];
std::cout << AC::ans1[p] << ' ' << AC::ans2[p] << '\n';
}
return 0;
}