阿狸的打字机

本文主要是介绍阿狸的打字机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

70分 裸的AC自动机

program type2;
typenode=recordson:array[0..25]of longint;fa,fail,key,e:longint;end;
var	a:array[1..100005]of node; sto:longint=1;st:array[1..100005]of char; len:longint;q,head,next:array[1..100005]of longint;ans,lk:array[1..100005]of longint; n:longint;ask:array[1..100005,0..2]of longint;m:longint;
function getfail(const x:longint):longint;
var	k,w:longint;
beginif (x=1)then exit(0);k:=a[x].key;w:=a[a[x].fa].fail;while (w>0)and(a[w].son[k]=0) do w:=a[w].fail;if w=0 then exit(1) else exit(a[w].son[k]);
end;
procedure buildac;
var	h,t,x,i:longint;
beginh:=0;t:=1;q[1]:=1;while h<t do begininc(h);x:=q[h];a[x].fail:=getfail(x);for i:=0 to 25 do if a[x].son[i]>0 then begininc(t);q[t]:=a[x].son[i];end;end;
end;
procedure init;	var ch:char; w,k,i:longint;
beginw:=1;while not eoln do begininc(len);read(ch);st[len]:=ch;case ch of'B':w:=a[w].fa;'P':begin inc(n); lk[n]:=w; a[w].e:=n; end;'a'..'z':begink:=ord(ch)-ord('a');if a[w].son[k]=0 then begininc(sto);a[w].son[k]:=sto;a[sto].fa:=w;a[sto].key:=k;end;w:=a[w].son[k];end;end;end;buildac;readln(m);for i:=1 to m do beginreadln(ask[i][0],ask[i][1]);//ask[i][0]:=lk[ask[i][0]];ask[i][1]:=lk[ask[i][1]];next[i]:=head[ask[i][1]];head[ask[i][1]]:=i;end;
end;
procedure solve; var w,x,i,p:longint;ch:char;
beginw:=1;for i:=1 to len do beginch:=st[i];case ch of'B':w:=a[w].fa;'P':beginfillchar(ans,sizeof(ans),0);if head[w]=0 then continue;p:=w;while w>1 do beginx:=w;while x>0 do beginif a[x].e>0 then inc(ans[a[x].e]);x:=a[x].fail;end;w:=a[w].fa;end;w:=p;x:=head[w];while x<>0 do beginask[x][2]:=ans[ask[x][0]];;x:=next[x];end;end;'a'..'z':w:=a[w].son[ord(ch)-ord('a')];end;end;for p:=1 to m do writeln(ask[p][2]);
end;
beginassign(input,'input.txt');reset(input);assign(output,'output.txt');rewrite(output);init;solve;close(input);close(output);
end.

满分程序（+dfs序优化）

program type2;
typenode=recordson:array[0..25]of longint;fa,fail,key,e:longint;end;heap=objects:array[1..100005]of longint;procedure add(x,k:longint);function sum(x:longint):longint;end;link=^Tnode;Tnode=recordx:longint;next:link;end;
var	sto:longint=1;
procedure push(var x:link; const t:longint);
var 	p:link;
beginnew(p); p^.x:=t; p^.next:=x; x:=p;
end;
procedure heap.add(x,k:longint);
beginwhile x<=sto do begininc(s[x],k);inc(x,x and (-x));end;
end;
function heap.sum(x:longint):longint;
beginsum:=0;while x>0 do begininc(sum,s[x]);dec(x,x and (-x));end;
end;(*	definitions	for 	useful	objects		*)var	a:array[0..100005]of node;st:array[1..100005]of char; len:longint;q,head,next:array[0..100005]of longint;ge:array[0..100005]of link;lk,ls,le:array[0..100005]of longint; n,tt:longint;ask:array[1..100005,0..2]of longint;m:longint; ans:Heap;
function getfail(const x:longint):longint;
var	k,w:longint;
beginif (x=1)then exit(0);k:=a[x].key;w:=a[a[x].fa].fail;while (w>0)and(a[w].son[k]=0) do w:=a[w].fail;if w=0 then exit(1) else exit(a[w].son[k]);
end;
procedure buildac;
var	h,t,x,i:longint;
beginh:=0;t:=1;q[1]:=1;while h<t do begininc(h);x:=q[h];a[x].fail:=getfail(x);if x<>1 then push(ge[a[x].fail],x);for i:=0 to 25 do if a[x].son[i]>0 then begininc(t);q[t]:=a[x].son[i];end;end;
end;
procedure DFS(const x:longint); var p:link;
begininc(tt);ls[x]:=tt;p:=ge[x];while p<>nil do beginDFS(p^.x);p:=p^.next;end;le[x]:=tt;
end;
procedure init;	var ch:char; w,k,i:longint;
beginw:=1;while not eoln do begininc(len);read(ch);st[len]:=ch;case ch of'B':w:=a[w].fa;'P':begin inc(n); lk[n]:=w; a[w].e:=n; end;'a'..'z':begink:=ord(ch)-ord('a');if a[w].son[k]=0 then begininc(sto);a[w].son[k]:=sto;a[sto].fa:=w;a[sto].key:=k;end;w:=a[w].son[k];end;end;end;buildac;DFS(1);readln(m);for i:=1 to m do beginreadln(ask[i][0],ask[i][1]);ask[i][0]:=lk[ask[i][0]];ask[i][1]:=lk[ask[i][1]];next[i]:=head[ask[i][1]];head[ask[i][1]]:=i;end;
end;
procedure solve; var w,x,i:longint;ch:char;
beginw:=1;for i:=1 to len do beginch:=st[i];case ch of'B':beginans.add(ls[w],-1);w:=a[w].fa;end;'P':beginx:=head[w];while x<>0 do beginask[x][2]:=ans.sum(le[ask[x][0]])-ans.sum(ls[ask[x][0]]-1);x:=next[x];end;end;'a'..'z':begin w:=a[w].son[ord(ch)-ord('a')]; ans.add(ls[w],1); end;end;end;for i:=1 to m do writeln(ask[i][2]);
end;
beginassign(input,'input.txt');reset(input);assign(output,'output.txt');rewrite(output);init;solve;close(input);close(output);
end.

这篇关于阿狸的打字机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---