ac自动机和有限状态

POJ1204（AC自动机模板题）题意：给一个N行长为M的字符串，给你一些需要去匹配的字符串，从任意一个字符串开始可以有八个方向，向上为A，顺时针依次是A——H，问你去匹配的字符串在给你的N*M 字符串中的坐标是怎么样的。

代码：const maxnodes=500000;var fx:array[1..8] of char=('E','F','G','H','A','B','C','D');t:array[0..maxnodes,'A'..'Z'] of longint;f,q,w:array[0..maxnodes] of longint;e:array[0..1001,0..1001] of char;s:array[0..1001] of char;colu,line:array[0..1] of longint;done:array[0..1001] of boolean;ans:array[0..1001] of record x,y,f:longint; end;n,m,num,u,i,j,k,l,r,root,size,x,y,p,li,co,tmp,len:longint;c:char;function nx(var x,y:longint; f:longint):char;begincase f of1:dec(x);2:begin dec(x); inc(y); end;3:inc(y);4:begin inc(x); inc(y); end;5:inc(x);6:begin inc(x); dec(y); end;7:dec(y);8:begin dec(x); dec(y); end;end;if (x<1)or(x>n)or(y<1)or(y>m) then exit('!');exit(e[x,y]);end;beginreadln(n,m,num);line[0]:=1;line[1]:=n;colu[0]:=1;colu[1]:=m;for i:=1 to n dobeginfor j:=1 to m do read(e[i,j]);readln;end;root:=0;size:=0;for i:=1 to num dobeginlen:=0;while not eoln dobegininc(len);read(s[len]);end;p:=root;for j:=len downto 1 dobeginc:=s[j];if t[p][c]=0 thenbegininc(size);t[p][c]:=size;end;p:=t[p][c];end;w[p]:=i;readln;end;l:=0;r:=0;for c:='A' to 'Z' doif t[root][c]<>0 thenbegininc(r);q[r]:=t[root][c];f[q[r]]:=root;end;while l<r dobegininc(l);u:=q[l];for c:='A' to 'Z' doif t[u][c]<>0 thenbegininc(r);q[r]:=t[u][c];p:=f[u];while (p<>root)and(t[p][c]=0) do p:=f[p];f[q[r]]:=t[p][c];end;end;for k:=1 to 8 dofor li:=0 to 1 dofor co:=1 to m dobeginx:=line[li];y:=co;p:=root;c:=e[x,y];while true dobeginwhile (p<>root)and(t[p][c]=0)do p:=f[p];p:=t[p][c];tmp:=p;while tmp<>root dobeginif (w[tmp]>0)and(not done[w[tmp]]) thenbeginans[w[tmp]].x:=x;ans[w[tmp]].y:=y;ans[w[tmp]].f:=k;done[w[tmp]]:=true;end;tmp:=f[tmp];end;c:=nx(x,y,k);if c='!' then break;end;end;for k:=1 to 8 dofor co:=0 to 1 dofor li:=1 to n dobeginx:=li;y:=colu[co];p:=root;c:=e[x,y];while true dobeginwhile (p<>root)and(t[p][c]=0)do p:=f[p];p:=t[p][c];tmp:=p;while tmp<>root dobeginif (w[tmp]>0)and(not done[w[tmp]]) thenbeginans[w[tmp]].x:=x;ans[w[tmp]].y:=y;ans[w[tmp]].f:=k;done[w[tmp]]:=true;end;tmp:=f[tmp];end;c:=nx(x,y,k);if c='!' then break;end;end;for i:=1 to num do writeln(ans[i].x-1,' ',ans[i].y-1,' ',fx[ans[i].f]);end.2、密码破译【问题描述】由于最近功课过于繁忙，Tim竟然忘记了自己电脑的密码，幸运的是Tim在设计电脑密码的时候，用了一个非常特殊的方法记录下了密码。

这个方法是：Tim把密码和其它的一些假密码共同记录在了一个本子上面。

为了能够从这些字符串中找出正确的密码，Tim又在另外一个本子上面写了一个很长的字符串，而正确的密码就是在这个字符串中出现次数最多的一个密码。

例如串ababa，假若密码是abab和aba，那么正确的密码是aba，因为aba在这个字符串中出现了2次。

现在你得到了Tim的这两个本子，希望你能够编写一个程序帮助Tim找出正确的密码。

【输入】输入由两个部分组成。

其中第一部分由若干行（<=5000）组成，每一行记录了一个密码，密码的均长度小于等于255位，并且都由小写字母组成。

然后一个空行，第二部分记录了一个很长的字符串，并且以’.’结束，其中只包含了小写字母。

【输出】输出文件名为Pass.out。

输出文件由仅有一行，为一个整数，表示正确密码在字符串中出现的次数。

如果这个出现次数为0，输出“No find”。

Pass.in Pass.out ab 6abcbdcabcdabcabcabcdbdabcbabdbcabdbdbdbd.程序：program pass;typepoint=^rec;rec=recorda:array['a'..'z']of point;e:{array[0..100]of }longint;fail,f:point;end;//这个是AC的数据结构，本人喜欢用动态int=longint;//这个是个人习惯varh,p,q:point;queue:array[1..200000]of point;i,j,k,m,n:int;f:array[1..6000]of int;st:ansistring;procedure neew(var P,father:point);//新建节点varch:char;beginnew(p);p^.e:=-1;for ch:='a'to'z'do p^.a[ch]:=nil;p^.f:=father;end;procedure insert(pos:int;st:ansistring);//插入vari,l:int;beginp:=h;i:=1;l:=length(st);while(i<=l)and(p^.a[st[i]]<>nil)do beginp:=p^.a[st[i]];inc(i);end;if i>l then beginp^.e:=pos;exit;while(i<=l)do beginneew(p^.a[st[i]],p);p:=p^.a[st[i]];inc(i);end;p^.e:=pos;end;procedure build;//建立字典树beginreadln(st);n:=0;neew(h,h);while(st<>'')do begininc(n);insert(n,st);readln(st);end;end;procedure failure;//构建失败指针varch:char;i,p,q:longint;k:point;procedure failure;//构建失败指针varch:char;i,p,q:longint;k:point;beginh^.fail:=h;p:=1;q:=0;for ch:='a'to 'z'doif(h^.a[ch]<>nil)then begininc(q);queue[q]:=h^.a[ch];h^.a[ch]^.fail:=h;end;while(p<=q)do beginfor ch:='a'to 'z'do if(queue[p]^.a[ch]<>nil)then begininc(q);queue[q]:=queue[p]^.a[ch];k:=queue[p]^.fail;while(k<>h)and(k^.a[ch]=nil)do k:=k^.fail;if k^.a[ch]=nil then queue[q]^.fail:=helse queue[q]^.fail:=k^.a[ch];if(queue[q]^.fail^.e<>-1)then begink:=queue[q]^.fail;queue[q]^.e:=k^.e;end;end;inc(p);end;end;procedure main;beginp:=h;print(h);m:=length(st)-1;for i:=1 to m do beginif p^.a[st[i]]<>nil then beginp:=p^.a[st[i]];endelse beginwhile(p<>h)and(p^.a[st[i]]=nil)do p:=p^.fail;if(p^.a[st[i]]<>nil)then p:=p^.a[st[i]];end;if p^.e<>-1 then inc(f[p^.e]);end;end;beginassign(input,'pass.in');reset(input);assign(output,'pass.out');rewrite(output);build;readln(st);failure;main;j:=0;for i:=1 to n do if f[i]>j then j:=f[i];if j<>0 then write(j)else write('No find');close(input);close(output);end.Poj1625Poj2778题意和Poj1625基本类似只不过不是求具体答案而是求答案Mod 100000的值了由于舍去了高精度运算我们可以很容易的写出代码先由AC自动机构造出DFA 再在DFA上进行一遍DP方程同Pku 1625 注意求模题意：给定m个异常基因片段，在所有长度为N的DNA序列中如‘AAAAA....’,'ATTTTT....','ATCG...','CGTA...',.....中不包含异常序列的DNA个数mod 100000(十万)的值，这题题解是AC自动机和矩阵乘法，首先建立AC自动机program poj2778;type matrix=array[0..101,0..101]of int64;const mo=100000;var a:string;nodes,leng,i,j,point,m,n,top,x,tail,som,k:longint;ans:int64;b,g:matrix;son:array[0..101,0..4]of longint;off:array[0..101]of longint;code:array[0..101]of char;stack:array[0..110]of longint;comp:array[0..110]of boolean;procedure muti(a,b:matrix;var c:matrix);begin fillchar(c,sizeof(c),0);for i:=0 to nodes dofor j:=0 to nodes dobeginfor k:=0 to nodes doc[i,j]:=(a[i,k]*b[k,j]+c[i,j])mod mo;end;end;function anticode(a:char):longint;begin case a of'A':exit(1);'C':exit(2);'G':exit(3);'T':exit(4);else exit(0);end;end;beginreadln(m,n);fillchar(son,sizeof(son),$ff);for i:=1 to m dobeginreadln(a);leng:=length(a);point:=0;for j:=1 to leng dobeginif son[point,anticode(a[j])]<>-1thenpoint:=son[point,anticode(a[j])]elsebegininc(nodes);son[point,anticode(a[j])]:=nodes;code[nodes]:=a[j];point:=nodes;end;end;comp[point]:=true;end;top:=0;tail:=1;while top<tail dobegininc(top);x:=stack[top];for i:=1 to 4 doif son[x,i]<>-1thenbegininc(tail);stack[tail]:=son[x,i];if x=0 then continue;som:=off[x];repeatif son[som,i]<>-1thenbeginsom:=son[som,i];break;end;som:=off[som];until som<=0;if som=0thenif son[som,i]<>-1thensom:=son[som,i];if comp[som]then comp[son[x,i]]:=true;off[son[x,i]]:=som;end;end;top:=0;nodes:=0;while top<tail dobegininc(top);x:=stack[top];if comp[x] then continue;if x>nodes then nodes:=x;for i:=1 to 4 doif son[x,i]=-1thenbeginsom:=off[x];while (som>0)and(son[som,i]=-1) dobeginsom:=off[som];end;if (son[som,i]<>-1)and(not comp[son[som,i]])theninc(g[x,son[som,i]])elseif (som=0)and(son[som,i]=-1)theninc(g[x,0]);endelseif (son[x,i]<>-1)and(not comp[son[x,i]])theninc(g[x,son[x,i]]);end;for i:=0 to nodes dob[i,i]:=1;while (n>0) dobeginif (n and 1)>0thenmuti(b,g,b);n:=n>>1;muti(g,g,g);end;for i:=0 to nodes doans:=(ans+b[0,i])mod mo;writeln(ans);end.第二种题解：const maxn=100;maxm=50000;base=100000;var tr:array['A'..'Z']of longint;n,m,i,j,k,tt,h,t,p,root,ans:longint;s:array[1..maxn,1..4]of longint;opt:array[0..maxm,1..maxn]of longint;f,q:array[1..maxn]of longint;d:array[1..maxn]of boolean;ch:char;procedure allot(var x:longint);var i:longint;begininc(tt); x:=tt;d[x]:=false; f[x]:=0;for i:=1 to 4 dos[x][i]:=0;end;beginassign(input,'DNAS.in'); reset(input); assign(output,'DNAS2.out'); rewrite(output); tr['A']:=1; tr['C']:=2;tr['G']:=3; tr['T']:=4;readln(n,m);tt:=0; allot(root);for i:=1 to n dobeginp:=root;while not eoln dobeginread(ch);k:=tr[ch];if s[p][k]=0then allot(s[p][k]);p:=s[p][k];end;d[p]:=true;readln;end;h:=1; t:=0;f[root]:=root;for i:=1 to 4 doif s[root][i]=0then s[root][i]:=rootelse begininc(t);q[t]:=s[root][i];f[q[t]]:=root;end;while h<=t dobeginfor i:=1 to 4 dobeginp:=f[q[h]];while (p<>root)and(s[p][i]=0) dop:=f[p];if s[p][i]=0then p:=rootelse p:=s[p][i];if s[q[h]][i]=0then s[q[h]][i]:=pelse begininc(t);q[t]:=s[q[h]][i];if d[p] then d[q[t]]:=true;f[q[t]]:=p;end;end;inc(h);end;fillchar(opt,sizeof(opt),0);opt[0][root]:=1;for i:=0 to m-1 dofor j:=1 to tt dofor k:=1 to 4 dobeginn:=s[j][k];if not(d[j]) and not(d[n])then begint:=i+1;opt[t][n]:=(opt[t][n]+opt[i][j])mod base;end;end;ans:=0;for i:=1 to tt doans:=(ans+opt[m][i])mod base;writeln(ans);close(input); close(output);end.Poj3208:题意求所有合法解中排第K的解合法解是一个自然数包含子串"666"首先我们得知道求字典序排第K的问题的通用解法这类问题可以转化为求方案数然后O(kN)递推来解决先考虑最简单的方法由小到大枚举出所有方案然后得到第K个虽然时间复杂度很高但是却是我们O(kN)递推的基础首先可以用DP等方法求出指定前缀时的方案数对于每一个前缀搜索的策略是遍历这个前缀下所有的方案每枚举出一个解就让计数器+1 不断的逼近排名K的方案而有了求出的指定前缀的方案数我们就可以大步地累加计数器来逼近排名位为K的方案假设我们已经求出了前i-1位正在求第i位由字典序从小到大枚举第i位每枚举出一位我们就得到了一个长为i的前缀判断计数器加上前缀状况下的方案数是不是大于K大于就表明这一位就是当前枚举出的值否则让计数器加上方案数继续枚举这样复杂度就是O(kN)了k就是每一位可以取的值总数那么这个问题就转化为求解长度为指定前缀的串的总数通过前面几篇文章的几个问题我们知道具体走到DFA上的哪一个节点可以概括一个前缀所以建立一个DFA 包含串"666" 边为'0'-'9'的字符我们还是这样表示状态第一维关于步数第二维是节点Opt[i][j]表示走到j这个节点再走i步能包含666的方案数但是考虑到包含666这个条件比较模糊我们修改DFA 把666的词尾节点所有的边指向自己那么只要再走i步停留在词尾节点就可以了DP方程: Opt[i][j]=Sum{Opt[i-1][Next[j][k]]}初始条件: Opt[0][666词尾节点]=1这样这个问题就解决了Vars:array[1..4,0..9]of longint;opt:array[0..11,1..4]of int64;ans:array[1..11]of lngint;n,i,j,k,x,y,m,p,ca:longint;beginassign(input,'SomeDay.in');reset(input);assign(output,'SomeDay.out');rewrite(output);for i:=1 to 3 dobeginfor j:=0 to 9 dos[i][j]:=1;s[i][6]:=i+1;end;for j:=0 to 9 dos[4][j]:=4;opt[0][4]:=1;for i:=1 to 11 dofor j:=1 to 4 dofor k:=0 to 9 doopt[i][j]:=opt[i][j]+opt[i-1][s[j][k]];readln(ca);while ca>0 dobegindec(ca);readln(n);for i:=1 to 11 doif opt[i][1]>=n then break;m:=i; j:=0;n:=n-opt[i-1][1];p:=1;while i>0 dobeginif i=mthen k:=1else k:=0;for j:=k to 9 doif n>opt[i-1][s[p][j]]then n:=n-opt[i-1][s[p][j]]else break;ans[i]:=j;dec(i);p:=s[p][j];end;for i:=m downto 1 dowrite(ans[i]);writeln;end;close(input);close(output);end.Ac自动机练习题：Poj1652;poj3691;poj2825;poj3208。