牛客多校第三场 H 题题解

题意：给定长度为 $nn$ 的模式串 $SS$，和长度为 $mm$ 的权值数组 $\{w_i\}\backslash \{w\_i\backslash \}$。对于一个长度为 $mm$ 的串，$w_{i}w\_i$ 表示使用该串上第 $ii$ 个字符与 $SS$ 匹配可以获得 $w_{i}w\_i$ 的权值。$kk$ 次询问一个长度为 $mm$ 的串 $TT$ 与 $SS$ 的最大权值公共子串。$n,m,k\le 1\times 10^5,mq\le 1\times 10^{6}n\; ,m,k\backslash leq\; 1\backslash times\; 10^5,mq\backslash leq\; 1\backslash times10^6$。

解法：对 $SS$ 建立 SAM，然后对于每次询问都可以将 $TT$ 串拉上去跑，对于 $TT$ 串，每匹配一个字符，就可以通过 SAM 知道当前匹配了多长的字符串。此题为 SAM 经典应用之最长公共子串问题。因而问题转化成为了对于每个右端点 $rr$，有一个左边界 $ll$，然后问处于某个区间的最大连续子段和。维护 $ww$ 的前缀和，利用区间查询最小值的线段树即可通过。复杂度 $\mathcal{O}(n+n\log n)\backslash mathcal\; O(n+n\backslash log\; n)$。

#include <bits/stdc++.h>
using namespace std;
long long inf = 0x3f3f3f3f3f3f3f3fll;
class segment_tree
{
    int n;
    vector<long long> minimum;
    long long query(int place, int left, int right, int start, int end)
    {
        if (start <= left && right <= end)
            return minimum[place];
        long long ans = inf;
        int mid = (left + right) >> 1;
        if (start <= mid)
            ans = min(ans, query(place << 1, left, mid, start, end));
        if (end > mid)
            ans = min(ans, query(place << 1 | 1, mid + 1, right, start, end));
        return ans;
    }

public:
    void set(int n, vector<long long> &w)
    {
        this->n = n;
        minimum.resize(4 * n + 10);
        function<void(int, int, int)> build = [&](int place, int left, int right)
        {
            if (left == right)
            {
                minimum[place] = w[left];
                return;
            }
            int mid = (left + right) >> 1;
            build(place << 1, left, mid);
            build(place << 1 | 1, mid + 1, right);
            minimum[place] = min(minimum[place << 1], minimum[place << 1 | 1]);
        };
        build(1, 0, n);
    }
    long long query(int l, int r)
    {
        return query(1, 0, n, l, r);
    }
} tr;
vector<long long> pre;
class SAM
{
    const int shift = 97;
    struct node
    {
        int ch[26];
        int len;
        int father;
        long long cnt;
        node()
        {
            memset(ch, 0, sizeof(ch));
            len = father = cnt = 0;
        }
    } NIL;
    vector<node> t;
    int last, ind;
    void insert(int c)
    {
        int p = last;
        int np = last = ++ind;
        t.push_back(NIL);
        t[np].len = t[p].len + 1;
        t[np].cnt = 1;
        for (; p && !t[p].ch[c]; p = t[p].father)
            t[p].ch[c] = np;
        if(!p)
            t[np].father = 1;
        else
        {
            int q = t[p].ch[c];
            if (t[p].len + 1 == t[q].len)
                t[np].father = q;
            else
            {
                int nq = ++ind;
                t.push_back(t[q]);
                t[nq].cnt = 0;
                t[nq].len = t[p].len + 1;
                t[q].father = t[np].father = nq;
                for (; p && t[p].ch[c] == q; p = t[p].father)
                    t[p].ch[c] = nq;
            }
        }
    }
 
public:
    SAM(string s)
    {
        last = ind = 1;
        t.push_back(NIL);
        t.push_back(NIL);
        for (auto i : s)
            insert(i - shift);
    }
    long long query(string &s)
    {
        int place = 1, len = 0, n = s.length();
        long long ans = 0;
        for (int i = 0; i < n;i++)
        {
            while (place > 1 && !t[place].ch[s[i] - shift])
            {
                place = t[place].father;
                len = t[place].len;
            }
            if (!t[place].ch[s[i] - shift])
                continue;
            place = t[place].ch[s[i] - shift];
            len++;
            ans = max(ans, pre[i + 1] - tr.query(i + 1 - len, i + 1));
        }
        return ans;
    }
};
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, k;
    long long x;
    cin >> n >> m >> k;
    pre.resize(m + 1);
    string s, t;
    cin >> s;
    SAM solve(s);
    for (int i = 1; i <= m;i++)
    {
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    tr.set(n, pre);
    for (int i = 1; i <= k;i++)
    {
        cin >> t;
        cout << solve.query(t) << "\n";
    }
    return 0;
}