1. 题目

传送门=￣ω￣=

2. 题解

似乎有很多很妙的正解我就不讲了

可以想到把初始的串正着建一个 Trie（即匹配前缀），反着再建一个 Trie（后缀匹配）

然后维护每个 Trie 的节点的子树内的初始串出现情况，这个用线段树合并弄就行了。

询问就拿 s1 去前缀 Trie 里查询相应节点 a，s2 去后缀 Trie 里查询到相应节点 b, 再对 a 的线段树和 b 的线段树取交。

复杂度是 $O(nm)$的，太慢了 QwQ（不知道 BZOJ 上能不能过，反正最慢的点已经超过 1 秒了）

于是压个位，每 64 个状态压在一个线段树节点里，用二进制数字表示，再 $O(1)$做 Bit Count，复杂度 $O(\frac {nm} {64})$，5892 MS 秒跑过的 QwQ（最慢的点 600 MS 左右）

代码：

#include <bits/stdc++.h>

#define BW (64)
#define NS (2000005)
#define MS (2005)

using namespace std;

typedef unsigned long long ULL;

int n, m, nr, len, l1, l2;

char str[NS], s1[NS], s2[NS];

int ls[MS * 40], rs[MS * 40], sz;

ULL D[MS * 40];

void Insert(int x, int l, int r, int& a)
{
    if (!a) a = ++sz;
    if (l == r) {D[a] |= (1ull << (x % BW)); return;}
    int mid = (l + r) >> 1;
    if (x / BW <= mid) Insert(x, l, mid, ls[a]);
    else Insert(x, mid + 1, r, rs[a]);
}

void Merge(int& x, int& y, int l, int r)
{
    if (!x || !y) {x = (x | y); return;}
    ++sz, ls[sz] = ls[x], rs[sz] = rs[x], D[sz] = D[x], x = sz;
    if (l == r) {D[x] |= D[y]; return;}
    int mid = (l + r) >> 1;
    Merge(ls[x], ls[y], l, mid), Merge(rs[x], rs[y], mid + 1, r);
}

struct Trie
{
    int nxt[NS][26], sz, rt[NS];
    Trie() {sz = 1;}
    void insert(int id)
    {
        int a = 1;
        for (int i = 0; i < len; i += 1)
        {
            str[i] -= 'a';
            if (!nxt[a][str[i]]) nxt[a][str[i]] = ++sz;
            a = nxt[a][str[i]], str[i] += 'a';
        }
        Insert(id, 0, nr, rt[a]);
    }
    int Query(char (&s)[NS], int l)
    {
        int a = 1;
        for (int i = 0; i < l; i += 1)
            if (nxt[a][s[i] - 'a']) a = nxt[a][s[i] - 'a'];
            else return 0;
        return rt[a];
    }
    void Dfs(int a)
    {
        for (int i = 0; i < 26; i += 1)
            if (nxt[a][i])
                Dfs(nxt[a][i]), Merge(rt[a], rt[nxt[a][i]], 0, nr);
    }
} Pre, Suf;

int Bc[1 << 16], Bin;

void CalBit()
{
    Bin = (1 << 16) - 1;
    for (int i = 1; i <= Bin; i += 1)
        Bc[i] = Bc[i >> 1] + (i & 1);
}

inline int BitCnt(ULL a)
{
    int res = 0;
    while (a) res += Bc[a & Bin], a >>= 16;
    return res;
}

int Cross(int x, int y)
{
    if (!x || !y) return 0;
    return Cross(ls[x], ls[y]) + Cross(rs[x], rs[y]) + BitCnt(D[x] & D[y]);
}

int main(int argc, char const* argv[])
{
    scanf("%d", &n), nr = (n - 1) / BW, CalBit();
    for (int i = 0; i < n; i += 1)
    {
        scanf("%s", str), len = strlen(str);
        Pre.insert(i), reverse(str, str + len), Suf.insert(i);
    }
    Pre.Dfs(1), Suf.Dfs(1);
    scanf("%d", &m); int a, b, ans = 0;
    while (m--)
    {
        scanf("%s%s", s1, s2), l1 = strlen(s1), l2 = strlen(s2);
        reverse(s2, s2 + l2);
        for (int i = 0; i < l1; i += 1)
            s1[i] = ((int)(s1[i] - 'a') + ans) % 26 + 'a';
        for (int i = 0; i < l2; i += 1)
            s2[i] = ((int)(s2[i] - 'a') + ans) % 26 + 'a';
        a = Pre.Query(s1, l1), b = Suf.Query(s2, l2);
        if (!a || !b) printf("%d\n", ans = 0);
        printf("%d\n", ans = Cross(a, b));
    }
    return 0;
}