题目
题解
神仙题……
题目中给的限制就是两个字符串$A,B$如果相等，那么$lcp(A,B)+lcs(A,B)+k\ge \vert A\vert$（$lcp$表示最长公共前缀，$lcs$表示最长公共后缀
考虑建立$AC$自动机处理$lcp$和$lcs$（所以一上来就往$SAM,SA$上靠的就直接完蛋），$AC$自动机加入每个$p$和$p$的反串，然后把$s$和$s$的反串在$Trie$图上跑，如果下一个点$x$（设匹配了$L$位）无法匹配了，这个点的$fail$子树里$s$匹配过的点（设点集为$S$）表示有多少$s$里的位置和$p$的$lcp$位$L$，现在就要查$p$的$L+k+1$位和$s$中的多少子串$lcs=\vert p\vert-L-k$，即查询$p$的反串的$fail$子树里有多少$S+k+1$的点
现在问题就转化成了查询一个点$x$（当前匹配位置$i$代表的串在$AC$自动机上的对应点）对应点$y$（$i+k+1$位在反串上代表的串在$AC$自动机上的对应点）子树里有多少$x$子树里的有权值点（当前匹配位置$i$能在$s$中能匹配的子串位置在$AC$自动机上的对应点）对应在$y$子树的有权值的点（$i$能在$s$中匹配的位置$+k+1$对应在$s$反串中的位置在$AC$自动机上的对应点）的个数
直接用树状数组维护，进子树时记录当前答案$ans1$，出子树时记录当前答案$ans2$，答案就是$ans2-ans1$
还没完！发现这样求答案会有重复的部分，假设求出位置$i-1$的$i+k$答案了，如果$i$位还能在$s$上匹配，那么求出的$i+k+1$答案包含了$i-1$的答案了
举个例子，假设$p=$ababacc，$s=$ababaacc，$k=1$，当匹配第$2$位的时候，求出的答案应该是$1$，即ababa*c，但是发现在匹配第$1$位的时候已经求出这个答案了
所以求$i$的答案的时候会包含$i-1$的答案，所以最后答案是$\sum ans_i-ans_{i-1}$
其实理解想法的大致方向思路还是很清晰的，但是我上面那一堆话好像说的很混乱……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
using namespace std;
const int MAX=4e5+5,N=94;
int k,n,m,tot,cnt;
int s[MAX],s1[MAX],ans[MAX];
char S[MAX],a[MAX];
vector<int> Vec[MAX];
int lowbit(int x) {return x&-x;}
void change(int x,int *s=s) {for(int i=x;i<=cnt;++s[i],i+=lowbit(i));}
int ask(int x,int *s)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=s[i];
return ans;
}
int ask(int l,int r,int *s=s) {return ask(r,s)-ask(l-1,s);}
struct AC{
struct p{
int x,y;
}c[MAX];
struct q{
int l,r,id;
q(int L=0,int R=0,int ID=0) {l=L,r=R,id=ID;}
};
int num;
int fail[MAX],qu[MAX],h[MAX],id[MAX],siz[MAX],ER[MAX],RE[MAX];
int son[MAX][N];
vector<q> vec[MAX];
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num;}
void ins(int _n,int id)
{
for(int i=1,x=0;i<=_n;++i)
{
if(!son[x][a[i]-33]) son[x][a[i]-33]=++tot;
x=son[x][a[i]-33];
}
for(int i=_n,x=0;i>=1;--i)
{
if(!son[x][a[i]-33]) son[x][a[i]-33]=++tot;
ER[i]=x=son[x][a[i]-33];
}
ER[_n+1]=0;
for(int i=0,x=0;i+k<=_n;++i)
vec[x].push_back(q(ER[i+k+1],i?ER[i+k]:-1,id)),x=son[x][a[i+1]-33];
}
void GET_FAIL()
{
int hl=1,tl=0;
for(int i=0;i<N;++i)
if(son[0][i]) qu[++tl]=son[0][i];
while(hl<=tl)
{
int tt=qu[hl++];
add(fail[tt],tt);
for(int i=0;i<N;++i)
if(son[tt][i]) fail[son[tt][i]]=son[fail[tt]][i],qu[++tl]=son[tt][i];
else son[tt][i]=son[fail[tt]][i];
}
}
void dfs(int x=0)
{
id[x]=++cnt,siz[x]=1;
for(int i=h[x],y;i;i=c[i].x)
dfs(y=c[i].y),siz[x]+=siz[y];
}
void Dfs(int x=0)
{
for(q v:vec[x])
ans[v.id]-=ask(id[v.l],id[v.l]+siz[v.l]-1)-(v.r==-1?0:ask(id[v.r],id[v.r]+siz[v.r]-1,s1));
for(int v:Vec[x])
change(id[RE[v+k+1]]),change(id[RE[v+k]],s1);
for(int i=h[x];i;i=c[i].x)
Dfs(c[i].y);
for(q v:vec[x])
ans[v.id]+=ask(id[v.l],id[v.l]+siz[v.l]-1)-(v.r==-1?0:ask(id[v.r],id[v.r]+siz[v.r]-1,s1));
}
void Init()
{
GET_FAIL(),dfs();
for(int i=n,x=0;i>=1;--i)
RE[i]=x=son[x][S[i]-33];
for(int i=0,x=0;i+k<=n;++i)
Vec[x].push_back(i),x=son[x][S[i+1]-33];
Dfs();
}
}_A;
int main()
{
scanf("%d%s%d",&k,S+1,&m),n=strlen(S+1);
for(int i=1,_n;i<=m;++i)
{
scanf("%s",a+1),_n=strlen(a+1);
if(_n>k) _A.ins(strlen(a+1),i);
else ans[i]=n-_n+1;
}
_A.Init();
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
