FDUSC前刷刷题吧。。
本题每个询问就是说将询问串与主串每个后缀匹配，若匹配成功则结束，否则加上lcp的长度
对主串建立后缀树，并用主席树维护DFS序
对于每个询问串，找到最后走到的点fin_node（在边上就往下走），
并求出完成匹配的后缀的位置match（若匹配成功则是fin_node子树中的最小值，否则就是n）
然后从fin_node开始一直往上走，
每个节点对答案的贡献为该点子树中小于等于match的后缀的个数乘以这条边的长度，
答案最后再加上match
时间复杂度预处理$O(nlog n)$，询问$O(mlog n)$
#include<cstdio>
#include<cstring>
const int inf=1<<25,S=12,N=100010,M=1800010;
using namespace std;
char tmp[N];
int text[N],root,last,pos,need,remain,acnode,ace,aclen;
int n,m,i,fin_node,fin_len,match,ans;
int dfn,seq[N<<1],st[N<<1],en[N<<1];
int head[N<<1],tot,val[M],l[M],r[M];
int min(int a,int b){return a<b?a:b;}
struct node{int st,en,lk,son[S],f;int len(){return min(en,pos+1)-st;}}tree[N<<1];
int new_node(int st,int en=inf){
node nd;
nd.st=st;nd.en=en;
for(int i=nd.lk=0;i<S;i++)nd.son[i]=0;
tree[++last]=nd;
return last;
}
int acedge(){return text[ace];}
void addedge(int node){
if(need)tree[need].lk=node;
need=node;
}
bool down(int node){
if(aclen>=tree[node].len())return ace+=tree[node].len(),aclen-=tree[node].len(),acnode=node,1;
return 0;
}
void init(){
need=last=remain=ace=aclen=0;
root=acnode=new_node(pos=-1,-1);
}
void extend(int c){
text[++pos]=c;need=0;remain++;
while(remain){
if(!aclen)ace=pos;
if(!tree[acnode].son[acedge()])tree[acnode].son[acedge()]=new_node(pos),addedge(acnode);
else{
int nxt=tree[acnode].son[acedge()];
if(down(nxt))continue;
if(text[tree[nxt].st+aclen]==c){aclen++;addedge(acnode);break;}
int split=new_node(tree[nxt].st,tree[nxt].st+aclen);
tree[acnode].son[acedge()]=split;
tree[split].son[c]=new_node(pos);
tree[nxt].st+=aclen;
tree[split].son[text[tree[nxt].st]]=nxt;
addedge(split);
}
remain--;
if(acnode==root&&aclen)aclen--,ace=pos-remain+1;
else acnode=tree[acnode].lk?tree[acnode].lk:root;
}
}
bool search(){
int x=fin_node=root,i=1,j;
fin_len=0;
while(i<=n){
if(tree[x].son[tmp[i]-'0'+1]){
x=fin_node=tree[x].son[tmp[i]-'0'+1];
fin_len=0;
j=tree[x].st;
while(i<=n&&j<min(tree[x].en,pos+1))if(tmp[i]-'0'+1==text[j])i++,j++,fin_len++;else return 0;
}else return 0;
}
return 1;
}
void dfs(int x,int sum,int f){
tree[x].f=f;
sum+=tree[x].len();
seq[st[x]=++dfn]=tree[x].en==inf?pos-sum+1:-1;
for(int i=0;i<S;i++)if(tree[x].son[i])dfs(tree[x].son[i],sum,x);
en[x]=dfn;
}
int ins(int x,int a,int b,int c){
int y=++tot;
val[y]=val[x]+1;
if(a==b)return y;
int mid=(a+b)>>1;
if(c<=mid)l[y]=ins(l[x],a,mid,c),r[y]=r[x];else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c);
return y;
}
int ask(int x,int a,int b,int c){
if(!x)return 0;
if(b<=c)return val[x];
int mid=(a+b)>>1,t=ask(l[x],a,mid,c);
if(c>mid)t+=ask(r[x],mid+1,b,c);
return t;
}
int askmin(int x,int y){
int a=0,b=pos,mid;
while(1){
if(a==b)return a;
mid=(a+b)>>1;
if(val[l[y]]>val[l[x]])x=l[x],y=l[y],b=mid;else x=r[x],y=r[y],a=mid+1;
}
}
int main(){
init();
scanf("%d%s",&n,tmp+1);
for(i=1;i<=n;i++)extend(tmp[i]-'0'+1);extend(11);
dfs(root,0,0);
for(i=1;i<=dfn;i++)head[i]=~seq[i]?ins(head[i-1],0,pos,seq[i]):head[i-1];
scanf("%d",&m);
while(m--){
scanf("%s",tmp+1);n=strlen(tmp+1);
ans=match=search()?askmin(head[st[fin_node]-1],head[en[fin_node]]):pos;
if(fin_node!=root){
ans+=fin_len*(ask(head[en[fin_node]],0,pos,match)-ask(head[st[fin_node]-1],0,pos,match));
fin_node=tree[fin_node].f;
}
while(fin_node!=root){
ans+=tree[fin_node].len()*(ask(head[en[fin_node]],0,pos,match)-ask(head[st[fin_node]-1],0,pos,match));
fin_node=tree[fin_node].f;
}
printf("%d
",ans);
}
return 0;
}