“蔚来杯“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

输出：

25

Code

#include <bits/stdc++.h>
#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;
}