"Weilai Cup" 2022 Niuke summer multi school training camp 3 h.hacker sam+ segment tree /dp/ divide and conquer (without the largest sub segment and of the inspection interval)

H.Hacker

Topic analysis

Given the parent string and several substrings , The length of substring is fixed , Each position has a weight , It is required to find a continuous interval in the common substring of the substring and the parent string , Make the sum of weights of continuous intervals maximum , Find the maximum weight sum .

First, set up the parent string SAM, Then use the segment tree to maintain the maximum value of the static interval sum , Then each time the inserted string ：

We set two variables $v,l$, Indicates the current state and matching length respectively , In limine $v=t_0$ And $l=0$, That is, the match is an empty string .

Now let's describe how to add a character $T_i$ And recalculate the answer ：

• If there is one from $v$ To character $T_i$ The transfer of , We just need to move and let $l$ Self increase one .
• If there is no such transfer , We need to shorten the current matching part , This means that we need to transfer according to the suffix link ：

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

meanwhile , Need to shorten the current length . Obviously, we need to $l$ The assignment is $\mathrm{len}(v)$.

Every time you find a legal range , Query directly on the line segment tree and update the answer .

The data is very watery , You can live without shrinking , Here is a group of special examples made by friends ：

Input ：

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

Output ：

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;
}