这里学习AC自动机
其实对KMP和trie掌握好了之后很容易扩展成AC自动机的
这里运用了一个性质
由失配指针反向可以建成一棵fail树
x串在y串中的出现的次数即为在fail树上以x结尾节点为根的子树中有多少个节点属于y串，这很好理解
而推广到这题，在文章中出现的次数即为单词结尾节点为根的子树的规模
注意这道题有相同的单词
当初这题我是用后缀数组做的O(LlogL)
而自动机复杂度为O(L),快了很多
type node=record
po,next:longint;
end; var e:array[..] of node;
trie:array[..,'a'..'z'] of longint;
q,f,p,w:array[..] of longint;
v:array[..] of longint;
t,i,j,k,n,l,len:longint;
s:ansistring; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure bfs;
var x,y,h,r,j:longint;
c:char;
begin
h:=;
r:=;
for c:='a' to 'z' do
if trie[,c]> then
begin
add(,trie[,c]);
inc(r);
q[r]:=trie[,c];
end; while h<=r do
begin
x:=q[h];
for c:='a' to 'z' do
if trie[x,c]> then
begin
y:=trie[x,c];
inc(r);
q[r]:=y;
j:=f[x];
while (j>) and (trie[j,c]=) do j:=f[j];
f[y]:=trie[j,c];
add(trie[j,c],y);
end;
inc(h);
end;
end; procedure dfs(x:longint);
var i,y:longint;
begin
i:=p[x];
while i<> do
begin
y:=e[i].po;
dfs(y);
w[x]:=w[y]+w[x];
i:=e[i].next;
end;
end; begin
readln(n);
for i:= to n do
begin
readln(s);
j:=;
l:=length(s);
for k:= to l do
begin
if trie[j,s[k]]= then
begin
inc(t);
trie[j,s[k]]:=t;
end;
j:=trie[j,s[k]];
inc(w[j]);
end;
v[i]:=j;
end;
bfs;
dfs();
for i:= to n do
writeln(w[v[i]]);
end.
ac自动机
var h,rank,x,y,sum,sa:array[..] of longint;
f:array[..,..] of longint;
where,len,d:array[..] of longint;
now, k,ans,i,j,p,n,m,t,l,r:longint;
s,cc:ansistring;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function lcp(a,b:longint):longint;
var k:longint;
begin
k:=trunc(ln(b-a+)/ln());
exit(min(f[a,k],f[b-d[k]+,k]));
end; begin
readln(t);
for i:= to t do
begin
readln(cc);
where[i]:=length(s)+;
len[i]:=length(cc);
s:=s+cc;
if i<>t then s:=s+' ';
end;
{ for i:=1 to t do
writeln(where[i],' ',len[i]);}
n:=length(s);
for i:= to n do
begin
y[i]:=ord(s[i]);
inc(sum[y[i]]);
end;
m:=;
for i:= to do
inc(sum[i],sum[i-]);
for i:= to n do
begin
sa[sum[y[i]]]:=i;
dec(sum[y[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if y[sa[i]]<>y[sa[i-]] then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=;
while m<n do
begin
y:=rank;
fillchar(sum,sizeof(sum),);
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;
j:=j shl ;
m:=p;
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;
k:=trunc(ln(n)/ln());
d[]:=;
for i:= to k do
d[i]:=d[i-]*;
for i:= to n do
f[i,]:=h[i];
for j:= to k do
for i:= to n do
if i+d[j]-<=n then
begin
f[i,j]:=min(f[i,j-],f[i+d[j-],j-]);
end
else break;
for i:= to t do
begin
ans:=;
k:=-;
l:=;
now:=rank[where[i]];
r:=now-;
while l<=r do
begin
m:=(l+r) shr ;
if lcp(m+,now)>=len[i] then
begin
k:=m;
r:=m-
end
else l:=m+;
end;
if k<>- then ans:=ans+now-k;
l:=now+;
k:=-;
r:=n;
while l<=r do
begin
m:=(l+r) shr ;
if lcp(now+,m)>=len[i] then
begin
k:=m;
l:=m+;
end
else r:=m-;
end;
if k<>- then ans:=ans+k-now;
writeln(ans);
end;
end.
后缀数组