前言

谐音替换不是这样的。

你应该先构造字典树，带上哈希，再用什么扫描线之类的求答案。

你怎么直接拿 AC 自动机草过去了！！！

这题真好像谐音替换幻想中的自己。

思路

需要将正串和反串各建一个 AC 自动机。

假设目前文本串的第 $j$ 位能匹配到某一模式串第 $i$ 位的前缀，假设这时前缀正好匹配到极限了，那么文本串的的第 $j+k+1$ 位的往后必须与此模式串的从第 $i+k+1$ 位的后缀匹配。

先不管恰好不恰好全统计上去。

记录文本串第 $j$ 位和模式串第 $i$ 位在正串的 ACAM 位置分别为 u 和 v。

文本串第 $j+k+1$ 位和模式串第 $i+k+1$ 位在反串的 ACAM 位置分别为 x 和 y。

则需满足正串 fail 树中 u 在 v 的子树里，反串 fail 树中 x 在 y 的子树中才会对答案有贡献。

只要将所有子树 v 中的所有 u 对应的 x 权值加 1，再统计 y 子树的权值和。

显然可以一部分 dfs 一部分树状数组维护。

但答案是需要恰好的，只需要将并非恰好匹配的减去即可。

也就是减掉目前文本串的第 $j+1$ 位能匹配到某一模式串第 $i+1$ 位的前缀，且文本串的的第 $j+k+1$ 位的往后与此模式串的从第 $i+k+1$ 位的后缀匹配的个数。

代码

我感觉看代码更好理解吧，也许只是我讲不明白。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct st{
    int x,id,d;
};
vector < st > gb[N],ch[N];
int dfn[N],siz[N],dfn_cnt,ans[N];
struct tree{
    int c[N][2];
    inline tree(){memset(c,0,sizeof(c));}
    inline int lowbit(int x){
        return x&-x;
    }
    inline void change(int x,int d){
        for (int i=x;i<=dfn_cnt;i+=lowbit(i)) c[i][d]++;
    }
    inline int gbc(int x,int d){
        int ret=0;
        for (int i=x;i;i-=lowbit(i)) ret+=c[i][d];
        return ret;
    }
}tr;//高贵的树状数组
struct ACAM{
    int cnt,to[N][94],fail[N];
    vector < int > G[N];
    inline ACAM(){
        cnt=1;
        memset(to,0,sizeof(to));
        memset(fail,0,sizeof(fail));
    }
    inline void build(){
        queue < int > q;
        fail[1]=1;
        for (int i=0;i<94;i++)
            if (to[1][i]) fail[to[1][i]]=1,q.push(to[1][i]);
            else to[1][i]=1;
        while (q.size()){
            int u=q.front();q.pop();
            G[fail[u]].push_back(u);
            for (int i=0;i<94;i++){
                if (to[u][i]) fail[to[u][i]]=to[fail[u]][i],q.push(to[u][i]);
                else to[u][i]=to[fail[u]][i];
            }
        }
    }
}A,B;
inline void dfs_pre(int x){
    dfn[x]=++dfn_cnt,siz[x]=1;
    for (auto v:B.G[x]) dfs_pre(v),siz[x]+=siz[v];
}
inline void dfs(int x){
    for (auto tmp:gb[x]) ans[tmp.id]+=(tmp.d==1?-1:1)*(tr.gbc(dfn[tmp.x]+siz[tmp.x]-1,tmp.d)-tr.gbc(dfn[tmp.x]-1,tmp.d));//把非子树内的贡献减去
    for (auto tmp:ch[x]) tr.change(dfn[tmp.x],tmp.d);
    for (auto v:A.G[x]) dfs(v);
    for (auto tmp:gb[x]) ans[tmp.id]+=(tmp.d==1?1:-1)*(tr.gbc(dfn[tmp.x]+siz[tmp.x]-1,tmp.d)-tr.gbc(dfn[tmp.x]-1,tmp.d));//加上所有贡献
}
int p,p1[N],p2[N];
char str[N],s[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int len,n,q,m;cin>>len>>(str+1)>>q;n=strlen(str+1);
    for (int id=1;id<=q;id++){
        cin>>(s+1);m=strlen(s+1);
        if (m<=len){ans[id]=n-m+1;continue;}//高贵特判
        p1[0]=p1[m+1]=p=1;
        for (int i=1;i<=m;i++){
            int c=s[i]-33;
            if (!A.to[p][c]) A.to[p][c]=++A.cnt;
            p1[i]=p=A.to[p][c];
        }
        p2[0]=p2[m+1]=p=1;
        for (int i=m;i;i--){
            int c=s[i]-33;
            if (!B.to[p][c]) B.to[p][c]=++B.cnt;
            p2[i]=p=B.to[p][c];
        }
        //建正串和反串 ACAM 并记录 v 和 y
        for (int i=0;i<=m-len;i++) gb[p1[i]].push_back({p2[i+len+1],id,1});
        for (int i=1;i<=m-len;i++) gb[p1[i]].push_back({p2[i+len],id,0});// 算两个东西 两个东西用他们分别的树状数组
        //将询问离线挂在节点上
    }
    A.build(),B.build();
    p=p1[0]=p1[n+1]=1;
    for (int i=1;i<=n;i++) p1[i]=p=A.to[p][str[i]-33];
    p=p2[0]=p2[n+1]=1;
    for (int i=n;i;i--) p2[i]=p=B.to[p][str[i]-33];
    //记录 u 和 v
    for (int i=0;i<=n-len;i++) ch[p1[i]].push_back({p2[i+len+1],0,1});
    for (int i=1;i<=n-len;i++) ch[p1[i]].push_back({p2[i+len],0,0});
    //把修改挂节点上
    dfs_pre(1),dfs(1);
    for (int i=1;i<=q;i++) cout<<ans[i]<<'\n';//高贵的输出
    return 0;
}