“蔚来杯“2022牛客暑期多校训练营3 H.Hacker SAM+线段树/DP/分治(不带修查区间最大子段和)

H.Hacker

题目分析

给定母串以及若干子串，子串长度固定，每个位置都有一个权值，要求在子串和母串的公共子串中找到一个连续区间，使得连续区间的权值和最大，求最大权值和。

首先对母串建立SAM，然后用线段树维护静态区间和的最大值，然后每次对插入的字符串：

我们设置两个变量$v,l$，分别表示当前状态以及匹配长度，一开始 $v=t_0$ 且 $l=0$，即匹配为空串。

现在我们来描述如何添加一个字符 $T_i$ 并为其重新计算答案：

• 如果存在一个从 $v$ 到字符 $T_i$ 的转移，我们只需要转移并让 $l$ 自增一。
• 如果不存在这样的转移，我们需要缩短当前匹配的部分，这意味着我们需要按照后缀链接进行转移：

$$v=\mathrm{link}(v)$$

与此同时，需要缩短当前长度。显然我们需要将 $l$ 赋值为 $\mathrm{len}(v)$。

每次找到合法区间，直接线段树上查询并更新答案即可。

数据很水，不缩也能过，这里提供一组群友造的特殊样例：

输入：

11 11 1
aaaabbbaaaa
2 3 7 5 10 -2 0 10 2 4 0
aaaaaaaaaaa
1
2
3
4

输出：

25
1

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
const int INF = 1e9 + 7;

int ww[N];

#define ls rt << 1
#define rs rt << 1 | 1
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r

struct node{
	int w, lw, rw, maxw;
	node(){
		w = 0;
		lw = rw = maxw = -INF;
	}
	node operator+ (node b) const{
		node c;
		c.w = w + b.w;
		c.lw = max(lw, w + b.lw);
		c.rw = max(b.rw, b.w + rw);
		c.maxw = max(max(maxw, b.maxw), rw + b.lw);
		return c;
	}
}tree[N << 2];

void build(int rt, int l, int r){
    if(l == r){
        tree[rt].w = tree[rt].lw = tree[rt].rw = tree[rt].maxw = ww[l];
        return;
    }
    int mid = l + r >> 1;
    build(lson), build(rson);
    tree[rt] = tree[ls] + tree[rs];
}

node query(int rt, int l, int r, int L, int R){
    if(l >= L && r <= R) return tree[rt];
    int mid = l + r >> 1;
    node b, c;
    if(mid >= L) b = query(lson, L, R);
    if(mid < R) c = query(rson, L, R);
    return b + c;
}

struct state {
  int len, link;
  std::map<char, int> next;
};

const int MAXLEN = 100000;
state st[MAXLEN << 1];
int sz, last;

void sam_init() {
    st[0].len = 0;
    st[0].link = -1;
    sz++;
    last = 0;
}

void sam_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
        st[cur].link = q;
        } else {
        int clone = sz++;
        st[clone].len = st[p].len + 1;
        st[clone].next = st[q].next;
        st[clone].link = st[q].link;
        while (p != -1 && st[p].next[c] == q) {
            st[p].next[c] = clone;
            p = st[p].link;
        }
        st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

int ql, qr;
int n, m, k;

int get(const string &T) {
    int v = 0, l = 0, best = 0, bestpos = 0, ans = 0;
    for (int i = 0; i < T.size(); i++) {
        while (v && !st[v].next.count(T[i])) {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(T[i])) {
            v = st[v].next[T[i]];
            l++;
        }
        int nowl = i - l + 1, nowr = i;
        if(nowl <= nowr){
            int res = query(1, 1, m, nowl + 1, nowr + 1).maxw;
            ans = max(ans, res);
        }

    }
    return ans;
}

inline void solve(){
    cin >> n >> m >> k;
    string a; cin >> a;
    sam_init();
    for (int i = 0; i < a.size(); i++) sam_extend(a[i]);
    for(int i = 1; i <= m; i++) cin >> ww[i];
    build(1, 1, m);
    while(k--){
        string s; cin >> s;
        cout << get(s) << endl;
    }
    
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}
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