看到这道题一开始想到的是后缀数组+二分+rmq
类似bzoj3172
问每个串i在合并后的串出现了多少次
等价于有多少个后缀j，使得LCP(i,j)>=length(s[i])
但是想想又不对，要求求的是有多少人被点到，每个人点到多少次
可能有多个后缀j满足条件但其实都是一个人的名字的一部分
好像二分搞不动，只能顺着名次依次找，理论上极其极端的数据是可以卡掉
但是实际却过了，，内疚啊……
UPD：太神了，这题有非暴力的做法，orz http://oi.nks.edu.cn/showmessage?message_id=4091
const inf=;
var s,sum,be,h,x,y,rank,sa:array[..] of longint;
q,len,w:array[..] of longint;
v:array[..] of boolean;
tot,c,p,m,n,t,l,i,j:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure suffix(n:longint);
var m:longint;
begin
for i:= to t do
inc(sum[s[i]]);
m:=inf;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[s[i]]]:=i;
dec(sum[s[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if (s[sa[i]]<>s[sa[i-]]) then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=;
while m<n do
begin
fillchar(sum,sizeof(sum),);
y:=rank;
p:=;
for i:=n-j+ to n do
begin
inc(p);
x[p]:=i;
end;
for i:= to n do
if sa[i]>j then
begin
inc(p);
x[p]:=sa[i]-j;
end; for i:= to n do
begin
rank[i]:=y[x[i]];
inc(sum[rank[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[rank[i]]]:=x[i];
dec(sum[rank[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if (y[sa[i]]<>y[sa[i-]]) or (y[sa[i]+j]<>y[sa[i-]+j]) then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=j shl ;
end;
h[]:=;
p:=;
for i:= to n do
begin
if rank[i]= then continue;
j:=sa[rank[i]-];
while s[i+p]=s[j+p] do inc(p);
h[rank[i]]:=p;
if p> then dec(p);
end;
end; begin
readln(n,m);
for i:= to n do
begin
read(l);
for j:= to l do
begin
inc(t);
read(s[t]);
be[t]:=i;
end;
inc(t);
s[t]:=inf; //注意姓和名之间也要加分隔符，防止点名串一部分在姓，一部分在名的情况
read(l);
for j:= to l do
begin
inc(t);
read(s[t]);
be[t]:=i;
end;
inc(t);
s[t]:=inf;
end;
for i:= to m do
begin
read(len[i]);
w[i]:=t+;
for j:= to len[i] do
begin
inc(t);
read(s[t]);
be[t]:=i+n;
end;
inc(t);
s[t]:=inf;
end;
suffix(t);
fillchar(sum,sizeof(sum),);
tot:=;
for i:= to m do
begin
for j:= to tot do //小小优化
v[q[j]]:=false;
tot:=;
j:=rank[w[i]];
l:=;
while j<=t do //找名次比点名串大的后缀
begin
inc(j);
c:=sa[j];
l:=min(h[j],l); //height数组和LCP的关系
if l<len[i] then break
else begin
if (be[c]>=) and (be[c]<=n) and not v[be[c]] then
begin
v[be[c]]:=true; //不能重复统计
inc(tot);
q[tot]:=be[c];
inc(sum[be[c]]);
end;
end;
end;
j:=rank[w[i]];
l:=h[j];
while j> do //找名次比点名串小的后缀
begin
dec(j);
c:=sa[j];
if l<len[i] then break
else begin
if (be[c]>=) and (be[c]<=n) and not v[be[c]] then
begin
v[be[c]]:=true;
inc(tot);
q[tot]:=be[c];
inc(sum[be[c]]);
end;
end;
l:=min(l,h[j]);
end;
writeln(tot);
end;
for i:= to n do
begin
write(sum[i]);
if i<>n then write(' ');
end;
writeln;
end.