题解：P13531 [OOI 2023] A task for substrings / 字符串问题

Toorean · 2026-01-20 19:12:33 · 题解

给出字符串集合 S 与字符串 t。多次询问，每次询问给出 (l,r)，查询 f(t[l,r])。其中 f(t[l,r]) 表示满足 [a,b]\subseteq[l,r] 的点对 (a.b) 使得存在 s_i\in S，s_i= t[a,b] 的点对数量。

考虑记录前缀答案，即设 a_i=\sum\limits_{j=1}^i[ t[j,i]\in S]，容易用 ACAM 建出的 fail 树上维护，答案应该是 \sum\limits_{i=l}^r a_i，但是会多算 a<l\le b\le r 的情况。

设 j 为最大的使得 a_j 统计了上述非法情况的下标，那么所求即为 f(t[l,j])+\sum\limits_{k=j+1}^r a_k。这部分可以直接用线段树二分求出。

由于存在这样的 a_j，故 t[l,j] 必然是某个 s_k\in S 的后缀。考虑建出反串的 ACAM，问题就转化成对前缀 s_{{rev_k}}[1,j-l+1] 查询所有 s_{rev}\in S_{rev} 出现次数和。十分容易处理，设 f_u 表示在 fail 树上 u 到根终止节点个数，g_u 表示在 trie 树上 u 到根的 f_v 之和，那么倍增找一下对应的前缀节点 v，g_v+\sum\limits_{k=j+1}^r a_k 即所求。

::::info[code]

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using ll = long long;

using namespace std;

const int N = 1e6 + 10;

int n, m;
string T, S;
int corp[N * 5];
ll f[N], a[N * 5];

struct ACAM {
    int tot, ch[26][N], fail[N], id[N], bel[N];
    ll cnt[N];
    int cch[26][N];
    int pa[22][N], dep[N];
    int mxlen[N];
    ACAM () { tot = 0; memset (ch, 0, sizeof ch), memset (cnt, 0, sizeof cnt); memset (fail, 0, sizeof fail); memset (mxlen, 0, sizeof mxlen); memset (id, 0, sizeof id); }
    void insert (int idd, string s) {
        int p = 0;
        for (auto now : s) {
            now -= 'a';
            if (!ch[now][p]) ch[now][p] = ++ tot;
            pa[0][ch[now][p]] = p;
            p = ch[now][p];
        }
        cnt[p] ++;
        mxlen[p] = s.size ();
        id[p] = idd;
        bel[idd] = p;
    }

    void build () {
        queue <int> q;
        for (int i = 0; i < 26; i ++) if (ch[i][0]) q.push (ch[i][0]);
        while (!q.empty ()) {
            int u = q.front (); q.pop ();
            cnt[u] += cnt[fail[u]];
            if (mxlen[fail[u]] > mxlen[u]) 
                mxlen[u] = max (mxlen[u], mxlen[fail[u]]),
                id[u] = id[ fail[u] ];
            for (int i = 0; i < 26; i ++)
                if (ch[i][u]) fail[ch[i][u]] = ch[i][fail[u]], q.push (ch[i][u]);
                else          ch[i][u] = ch[i][fail[u]];
        }
    }

    int getfa (int u, int d) {
        int delta = dep[u] - d;
        for (int i = 20; ~i; i --) if (delta >> i & 1) u = pa[i][u];
        return u;
    }
} ord, rev;

struct BS_sgt {
    #define ls (x << 1)
    #define rs (x << 1 | 1)
    #define mid (l + r >> 1)

    vector <int> mn;
    int n;
    BS_sgt (int x = 0): n (x) { mn.assign (x + 6 << 2, 1e9); }
    void assign (int p, int k, int x, int l, int r) {
        mn[x] = min (mn[x], k);
        if (l == r) return ;
        if (p <= mid) assign (p, k, ls, l, mid);
        else          assign (p, k, rs, mid + 1, r);
    }
    void assign (int p, int k) { assign (p, k, 1, 1, n); }
    int qry (int k, int R, int x, int l, int r) {
        // fprintf (stderr, "now queried[%d, %d] for %d, %d, min = %d\n", l, r, k, R, mn[x]);
        if (mn[x] > k) return -1;
        if (l == r) return l;
        int res = -1;
        if (mid + 1 <= R && mn[rs] <= k) res = qry (k, R, rs, mid + 1, r);
        if (res == -1)                   res = qry (k, R, ls, l, mid);
        return res;
    }
    int qry (int k, int r) { return qry (k, r, 1, 1, n); }
};

void dfs (int u) {
    for (int i = 1; i <= 20; i ++) rev.pa[i][u] = rev.pa[i - 1][ rev.pa[i - 1][u] ];
    for (int i = 0; i < 26; i ++) if (rev.cch[i][u]) f[rev.cch[i][u]] += f[u], rev.dep[rev.cch[i][u]] = rev.dep[u] + 1, dfs (rev.cch[i][u]); 
}

int main (void) {

    ios :: sync_with_stdio (false);
    cin.tie (nullptr);

    cin >> n >> m >> T; T = ' ' + T; int sizt = T.size () - 1;
    for (int i = 1; i <= n; i ++) {
        cin >> S;
        ord.insert (i, S);
        reverse (S.begin (), S.end ());        
        rev.insert (i, S);
    } memcpy (rev.cch, rev.ch, sizeof rev.cch);
    ord.build (), rev.build ();
    memcpy (f, rev.cnt, sizeof f);
    dfs (0);
    int p = 0; BS_sgt sgt (sizt);
    for (int i = 1; i <= sizt; i ++) {
        p = ord.ch[ T[i] - 'a' ][p];
        corp[i] = p;
        a[i] = ord.cnt[p];
        a[i] += a[i - 1];
        sgt.assign (i, i - ord.mxlen[p] + 1);
        // fprintf (stderr, "minl of prefix %d is %d\n", i, i - ord.mxlen[p] + 1);
    }

    while (m --) {
        int l, r; cin >> l >> r;
        int ff = sgt.qry (l - 1, r);
        // fprintf (stderr, "r for query [%d, %d] is %d\n", l, r, ff);
        if (ff < l) printf ("%lld ", a[r] - a[l - 1]);
        else {
            int id = ord.id[ corp[ff] ];
            // fprintf (stderr, "ff = %d (id = %d) and first part = %lld, second part = %lld (anc = %d)\n", ff, id, a[r] - a[ff], f[ rev.getfa (rev.bel[id], ff - l + 1) ], rev.getfa (rev.bel[id], ff - l + 1));
            printf ("%lld ", a[r] - a[ff] + f[ rev.getfa (rev.bel[id], ff - l + 1) ]);
        }
    }

    return 0;
}

::::