前缀和与后缀相同

解析

我们注意到不管是数据还是询问，只要能对上，那肯定是前缀相同后缀相同，中间有一段不同的修改，我们预处理出每一对中间的实际转换的内容，容易发现，实际产生贡献的询问和转换串，中间的修改肯定是完全相同的，而转换串两边的前后缀分别是询问串前缀的后缀和后缀的前缀，也就是被包含在询问串的中间。那么，我们对中间的转换哈希一下，然后对于任何中间相同的串，我们对前缀和后缀分别建好 trie，这样对每个询问，就相当于查询两边的 trie 上都是当前点的祖先的点有几个。对于这个问题，我们可以对 trie 计算 dfs 序之后将其转换为二维数点问题，使用树状数组即可维护，最终的总复杂度为 $(O(|S|+|T|+(q+n)\log(q+n)))$ 。

答案

#include <bits/stdc++.h>
using namespace std;

using i64 = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;

const i64 P = 1'000'000'000'000'000'003, b = 1'000'000'007;
i64 get_hash(string s)
{
    i64 v = 0;
    for (auto x : s)
        v = (i128(v) * b + x) % P;
    return v;
}

const int N = 200005;
int n, q, ans[N];
string s1[N], s2[N], t1[N], t2[N];
i64 vs[N], vt[N];
pii os[N], ot[N];
map<i64, vector<int>> ms, mt;

const int M = 2500005;
int ch[M][26], tot, dfn, ord[M], ed[M];
void clear()
{
    while (tot)
    {
        memset(ch[tot], 0, sizeof ch[tot]);
        --tot;
    }
    tot = 2;
    dfn = 0;
}
int insert(int p, const string &s)
{
    for (auto c : s)
    {
        int &q = ch[p][c - 'a'];
        if (!q)
            q = ++tot;
        p = q;
    }
    return p;
}
int get_id(int p, const string &s)
{
    for (auto c : s)
    {
        int q = ch[p][c - 'a'];
        if (q)
        {
            p = q;
        }
        else
        {
            break;
        }
    }
    return p;
}

i64 work(string &s1, string &s2)
{
    int n = s1.length();
    int l = 0, r = n - 1;
    while (l < n && s1[l] == s2[l])
        ++l;
    if (l == n)
        return 0;
    while (s1[r] == s2[r])
        --r;
    assert(l <= r);
    i64 v = get_hash(s1.substr(l, r - l + 1) + s2.substr(l, r - l + 1));
    s1 = s2.substr(0, l);
    reverse(s1.begin(), s1.end());
    s2 = s2.substr(r + 1, n - r - 1);
    return v;
}

void dfs(int u)
{
    ord[u] = ++dfn;
    for (int c = 0; c < 26; ++c)
    {
        if (ch[u][c])
            dfs(ch[u][c]);
    }
    ed[u] = dfn;
}

namespace BIT
{
    int c[M];
    void clear()
    {
        memset(c + 1, 0, tot * 4);
    }
    void modify(int p, int x)
    {
        for (; p <= tot; p += p & -p)
            c[p] += x;
    }
    void modify(int l, int r, int x)
    {
        modify(l, x);
        modify(r + 1, -x);
    }
    int query(int p)
    {
        int res = 0;
        for (; p; p -= p & -p)
            res += c[p];
        return res;
    }
}

struct node
{
    int x, y, z;
    node() {}
    node(int x, int y, int z) : x(x), y(y), z(z) {}
};
vector<node> mdf[M];
vector<pii> qry[M];

void add_mdf(int l1, int r1, int l2, int r2)
{
    mdf[l1].emplace_back(l2, r2, 1);
    mdf[r1 + 1].emplace_back(l2, r2, -1);
}
void add_qry(int x, int y, int id)
{
    qry[x].emplace_back(y, id);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    {
        cin >> s1[i] >> s2[i];
        vs[i] = work(s1[i], s2[i]);
        ms[vs[i]].push_back(i);
    }
    for (int i = 1; i <= q; ++i)
    {
        cin >> t1[i] >> t2[i];
        if (t1[i].length() != t2[i].length())
            continue;
        vt[i] = work(t1[i], t2[i]);
        mt[vt[i]].push_back(i);
    }

    // cerr << "?" << endl;

    for (const auto &[v, a] : ms)
    {
        if (!mt.count(v))
            continue;
        const auto &b = mt[v];
        assert(v);
        clear();
        for (auto i : a)
        {
            os[i] = pii(insert(1, s1[i]), insert(2, s2[i]));
        }
        for (auto i : b)
        {
            ot[i] = pii(get_id(1, t1[i]), get_id(2, t2[i]));
        }
        dfs(1), dfs(2);

        // cerr << "? " << v << " " << tot << " " << dfn << endl;

        for (int i = 1; i <= dfn; ++i)
            mdf[i].clear(), qry[i].clear();
        for (auto i : a)
        {
            auto [u, v] = os[i];
            add_mdf(ord[u], ed[u], ord[v], ed[v]);
        }
        for (auto i : b)
        {
            auto [u, v] = ot[i];
            add_qry(ord[u], ord[v], i);
        }

        BIT::clear();
        for (int i = 1; i <= dfn; ++i)
        {
            for (auto [l, r, x] : mdf[i])
                BIT::modify(l, r, x);
            for (auto [x, id] : qry[i])
                ans[id] = BIT::query(x);
        }
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";

    return 0;
}