SAM好题，显然我们不能与每个后缀都去算LCP
考虑对询问串每一位算贡献，先构建出逆序构建自动机，这样我们得到了原串的后缀树（parent树）
根据parent树的定义，一个节点对应字符串出现的位置对应该节点的right集合也就是子树right集合的并
某些节点代表了一个后缀，我们从开头到结尾编号为1~n；这样求出每个节点的子树内，代表后缀的节点所代表的后缀编号最小是多少，记作mi[]
然后对于每个询问串在自动机上匹配（逆序），设最终匹配到的点为x
由于每个子串一定是某个后缀的某个前缀
如果匹配成功了，说明匹配到mi[x]这个后缀就结束了，否则会一直匹配下去，我们假设匹配到n+1结束
设最终匹配到的后缀为m，显然，从x到root上我们计算每条边的贡献
对于边(fa[a],a)，边上的每个字符的比较次数贡献显然就是a子树内代表后缀编号小于等于m的节点个数
裸的想法可以用dfs序+主席树来完成
最后我们答案还要+x-1，因为比较失败也算是一次比较……
type node=record
po,next:longint;
end;
point=record
l,r,s:longint;
end; var tree:array[..*] of point;
e:array[..] of node;
go:array[..,''..''] of longint;
mi,b,h,p,l,r,fa,mx,w:array[..] of longint;
cl,n,m,x,y,i,j,k,last,t,len:longint;
fl:boolean;
s:ansistring;
ans:int64; function lowbit(x:longint):longint;
begin
exit(x and (-x));
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure ins(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure add(c:char);
var p,q,np,nq:longint;
begin
p:=last;
inc(t); np:=t; last:=t;
mx[np]:=mx[p]+;
w[np]:=i;
while (p<>) and (go[p,c]=) do
begin
go[p,c]:=np;
p:=fa[p];
end;
if p= then fa[np]:=
else begin
q:=go[p,c];
if mx[q]=mx[p]+ then fa[np]:=q
else begin
inc(t); nq:=t;
mx[nq]:=mx[p]+;
go[nq]:=go[q];
fa[nq]:=fa[q];
fa[q]:=nq; fa[np]:=nq;
while go[p,c]=q do
begin
go[p,c]:=nq;
p:=fa[p];
end;
end;
end;
end; procedure dfs(x:longint);
var i,y:longint;
begin
inc(len);
b[len]:=x;
mi[x]:=w[x];
if w[x]= then mi[x]:=;
// writeln(x,' ',fa[x],':',w[x]);
l[x]:=len;
i:=p[x];
while i<> do
begin
y:=e[i].po;
dfs(y);
mi[x]:=min(mi[x],mi[y]);
i:=e[i].next;
end;
r[x]:=len;
// writeln(mi[x]);
end; function build(l,r:longint):longint;
var m,q:longint;
begin
inc(len);
if l=r then exit(len)
else begin
q:=len;
m:=(l+r) shr ;
tree[q].l:=build(l,m);
tree[q].r:=build(m+,r);
exit(q);
end;
end; function work(l,r,last,x:longint):longint;
var m,q:longint;
begin
inc(len);
q:=len;
if l=r then tree[q].s:=tree[last].s+
else begin
m:=(l+r) shr ;
if x<=m then
begin
tree[q].r:=tree[last].r;
tree[q].l:=work(l,m,tree[last].l,x);
end
else begin
tree[q].l:=tree[last].l;
tree[q].r:=work(m+,r,tree[last].r,x);
end;
tree[q].s:=tree[tree[q].l].s+tree[tree[q].r].s;
end;
exit(q);
end; function ask(l,r,p,q:longint):longint;
var m:longint;
begin
if (x>=r) then exit(tree[q].s-tree[p].s)
else begin
m:=(l+r) shr ;
if x<=m then exit(ask(l,m,tree[p].l,tree[q].l))
else exit(tree[tree[q].l].s-tree[tree[p].l].s+ask(m+,r,tree[p].r,tree[q].r));
end;
end; begin
readln(n);
readln(s);
last:=; t:=;
for i:=n downto do
add(s[i]);
for i:= to t do
if fa[i]<> then ins(fa[i],i);
len:=;
dfs();
readln(m);
len:=;
h[]:=build(,n);
for i:= to t do
if w[b[i]]= then h[i]:=h[i-]
else h[i]:=work(,n,h[i-],w[b[i]]);
for i:= to m do
begin
readln(s);
len:=length(s);
j:=;
fl:=true;
cl:=;
for k:=len downto do
if go[j,s[k]]= then
begin
while (go[j,s[k]]=) and (j>) do
begin
j:=fa[j];
cl:=mx[j];
end;
if j= then j:=
else begin
inc(cl);
j:=go[j,s[k]];
end;
fl:=false;
end
else begin
inc(cl);
j:=go[j,s[k]];
end; //cl表示询问串从头开始最长匹配的长度
if fl then x:=mi[j] else x:=n+;
ans:=;
if j> then
begin
y:=cl-mx[fa[j]]; // 这里要注意
ans:=ans+int64(y)*int64(ask(,n,h[l[j]-],h[r[j]]));
j:=fa[j];
end;
while j> do
begin
y:=mx[j]-mx[fa[j]];
ans:=ans+int64(y)*int64(ask(,n,h[l[j]-],h[r[j]]));
j:=fa[j];
end;
writeln(ans+x-);
end;
end.