时间复杂度是 $O(\sum |S_i|)$。

思路就是把串复制两边然后再拼起来，把这个作为文本串。

模式串就是后缀加上前缀。

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

const int maxn = 2e5 + 10;
const int maxm = 5e6 + 10;
namespace ACAM
{
    int ch[maxm][10];
    int ans[maxn];
    int getid(char c)
    {
        if(c == 'A')return 1;
        if(c == 'G')return 2;
        if(c == 'U')return 3;
        if(c == 'C')return 4;
        if(c == '*')return 5;
        return 6;
    }
    int fail[maxm],val[maxm];
    vector<int> g[maxm];
    int cnt;
    struct edge
    {
        int nxt,to;
    }e[maxm];
    int head[maxm],tot;
    void add_edge(int u,int v)
    {
        e[++tot].nxt = head[u];
        head[u] = tot;
        e[tot].to = v;
    }
    void insert(string s,int i)
    {
        int p = 0;
        for(char si:s)
        {
            int i = getid(si);
            if(!ch[p][i])ch[p][i] = ++cnt;
            p = ch[p][i];
        }
        g[p].push_back(i);
    }
    void build()
    {
        queue<int> q;
        for(int i = 1;i <= 6;i++)
        {
            if(ch[0][i])q.push(ch[0][i]);
        }
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = 1;i <= 6;i++)
            {
                if(ch[u][i])
                {
                    fail[ch[u][i]] = ch[fail[u]][i];
                    q.push(ch[u][i]);
                }
                else ch[u][i] = ch[fail[u]][i];
            }
        }
    }
    void query(string S)
    {
        int p = 0;
        for(char si:S)
        {
            p = ch[p][getid(si)];
            val[p]++;
        }
    }
    void dfs(int u)
    {
        for(int i = head[u];i;i = e[i].nxt)
        {
            int v = e[i].to;
            dfs(v);
            val[u] += val[v];
        }
        for(auto i : g[u])ans[i] += val[u];
    }
    void getans()
    {
        for(int i = 1;i <= cnt;i++)add_edge(fail[i],i);
        dfs(0);
    }
}
string T;
int n,q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for(int i = 1;i <= n;i++)
    {
        string str;
        cin >> str;
        T = T + str + "#" + str + '*';
    }
    for(int i = 1;i <= q;i++)
    {
        string p,q;
        cin >> p >> q;
        ACAM::insert(q + '#' + p,i);
    }
    ACAM::build();
    ACAM::query(T);
    ACAM::getans();
    for(int i = 1;i <= q;i++)cout << ACAM::ans[i] << '\n';
    return 0;
}