思路与算法

设PA[i]为A从位置i开始的非空回文前缀数量，PB[j]为B在j结束的回文后缀数量，分别用Manacher半径对起止位置作区间差分求出，再取前缀和。查询l=x−1,r=|B|−y，取L=LCP(A[l..],reverse(B)[y−1..])。答案是L+Σ_{i=l+1}^{l+L}PA[i]+Σ_{j=r−L}^{r−1}PB[j]，越界计0。后缀数组+Kasai LCP+线段树RMQ精确求L，避免哈希碰撞。

正确性说明

若A[l]与B[r]不同，任何非空拼接都不回文。相同时剥掉这对外字符：两侧长度都1贡献1；只有A一侧剩空，贡献B内层所有回文后缀PB[r−1]；只有B剩空，贡献PA[l+1]；两侧都非空，递归为F(l+1,r−1)。四类不重不漏。能连续剥掉的匹配外字符对数正是反串LCP的L，累加递推得到公式。Manacher每个中心的一系列半径恰给每个可作回文起点/终点的位置一次贡献，差分统计正确；后缀数组相邻LCP区间最小值等于任意两后缀LCP。

复杂度

设L0=|A|+|B|，Manacher/差分/前缀和O(L0)，倍增计数排序后缀数组O(L0 log L0)，Kasai与RMQ树初始化O(L0)，Q次查询O(Q log L0)，空间O(L0)。

易错点

第1长指完整串；A_x是从x开始的后缀，B_y长度|B|−y+1。PA[l+L]或PB[r−L]可能越界，按0处理。按长度选择对计数，不按相同字符串去重；答案可达|A||B|，必须64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> pal(const string &s, bool starts) {
    int n = s.size();
    vector<int> d1(n), d2(n), dif(n + 1);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
            k++;
        d1[i] = k;
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
        int a = starts ? i - k + 1 : i, b = starts ? i : i + k - 1;
        dif[a]++;
        dif[b + 1]--;
    }
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k])
            k++;
        d2[i] = k;
        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
        if (k) {
            int a = starts ? i - k : i, b = starts ? i - 1 : i + k - 1;
            dif[a]++;
            dif[b + 1]--;
        }
    }
    vector<ll> p(n + 1);
    int v = 0;
    for (int i = 0; i < n; i++) {
        v += dif[i];
        p[i + 1] = p[i] + v;
    }
    return p;
}
struct LCP {
    int n;
    vector<int> rank, seg;
    LCP(string s) {
        s.push_back(char(0));
        n = s.size();
        vector<int> p(n), pn(n), cn(n), cnt(max(n, 256));
        rank.resize(n);
        for (unsigned char x : s)
            cnt[x]++;
        for (int i = 1; i < 256; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--)
            p[--cnt[(unsigned char)s[i]]] = i;
        int classes = 1;
        rank[p[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (s[p[i]] != s[p[i - 1]])
                classes++;
            rank[p[i]] = classes - 1;
        }
        for (int len = 1; len < n && classes < n; len <<= 1) {
            fill(cnt.begin(), cnt.begin() + classes, 0);
            for (int i = 0; i < n; i++) {
                pn[i] = p[i] - len;
                if (pn[i] < 0)
                    pn[i] += n;
                cnt[rank[pn[i]]]++;
            }
            for (int i = 1; i < classes; i++)
                cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; i--)
                p[--cnt[rank[pn[i]]]] = pn[i];
            int nc = 1;
            cn[p[0]] = 0;
            for (int i = 1; i < n; i++) {
                int a = p[i], b = p[i - 1];
                if (rank[a] != rank[b] || rank[(a + len) % n] != rank[(b + len) % n])
                    nc++;
                cn[a] = nc - 1;
            }
            rank.swap(cn);
            classes = nc;
        }
        seg.assign(2 * n, INT_MAX);
        int k = 0;
        for (int i = 0; i < n; i++) {
            int r = rank[i];
            if (!r)
                continue;
            int j = p[r - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])
                k++;
            seg[n + r] = k;
            if (k)
                k--;
        }
        for (int i = n - 1; i; i--)
            seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }
    int get(int a, int b) {
        if (a == b)
            return n - a - 1;
        int l = rank[a], r = rank[b];
        if (l > r)
            swap(l, r);
        int ans = INT_MAX;
        for (l = l + 1 + n, r = r + 1 + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                ans = min(ans, seg[l++]);
            if (r & 1)
                ans = min(ans, seg[--r]);
        }
        return ans;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string type, A, B;
    cin >> type >> A >> B;
    int n = A.size(), m = B.size();
    vector<ll> pa = pal(A, true), pb = pal(B, false);
    string rev = B;
    reverse(rev.begin(), rev.end());
    LCP table(A + "{" + rev);
    int Q;
    cin >> Q;
    while (Q--) {
        int x, y;
        cin >> x >> y;
        int l = x - 1, r = m - y, L = table.get(l, n + 1 + y - 1);
        L = min(L, min(n - l, r + 1));
        ll ans = L + pa[min(n, l + L + 1)] - pa[l + 1] + pb[r] - pb[max(0, r - L)];
        cout << ans << '\n';
    }
}