「2026 牛客多校 1」L. 子串的子串

发表于 分类于 本文字数： 972 阅读时长 ≈ 1 分钟

Description

Link：https://ac.nowcoder.com/acm/contest/133876/L

给出一个长度为 nn 的字符串 SS 和一个长度为 nn 的序列 a1,…,ana_1, \dots, a_n。有 QQ 次询问。每次询问给出一个字符串 tt：

如果一个区间 [l,r][l, r] (1≤l≤r≤n1 \leq l \leq r \leq n) 满足 tt 是 S[l:r]S[l : r] 的子串，那么称这个区间为好区间。

求所有好区间的区间和的最大值，以及所有好区间的区间和之和（对 998244353998244353 取模）。保证至少存在一个好区间。

数据范围：1≤n≤1051 \leq n \leq 10^5，1≤q≤3×1051 \leq q \leq 3\times 10^5，−109≤ai≤109-10^9 \leq a_i\leq 10^9，1≤∑∣t∣≤3×1051 \leq \sum |t| \leq 3\times 10^5。

时空限制：55s / 10241024MiB。

Solution

这个问题应该很难通过数据结构在线快速查询，所以才会启发选手想到暴力。

应该是一个比较经典的结论：将询问串 tt 去重之后，所有询问串 tt 在 SS 中的出现次数之和不超过 O(n∑∣t∣)O(n\sqrt{\sum |t|}) 级别。

因为本质不同的询问串长 ∣t∣|t| 不超过 O(∑∣t∣)\mathcal{O}(\sqrt{\sum |t|}) 级别，同一长度的询问串 endpos 各不相同。

对询问串建 AC 自动机（trie 图），每个节点记录一下向上跳 fail 指针遇到的最近询问节点 up。

然后从左到右扫描 SS，扫描到右端点 rr 时，维护以 rr 结尾的最长匹配串对应的状态。然后在当前状态不断地跳 up 指针，去更新（记录）询问串在 SS 中的 endpos。

记 T=∑∣t∣T = \sum |t|，时间复杂度 O(T∣Σ∣+nT)\mathcal{O}(T|\Sigma| + n\sqrt{T})，空间复杂度 O(T∣Σ∣)\mathcal{O}(T|\Sigma|)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#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;
}