下载文档原格式
ac自动机相关的题
（实用版）
目录
1.AC 自动机的基本概念
2.AC 自动机的工作原理
3.AC 自动机的应用领域
4.AC 自动机的发展前景
正文
一、AC 自动机的基本概念
AC 自动机，全称为 Autoregressive Combinatorial 自动机，即自
回归组合自动机，是一种用于生成具有特定统计特性的字符串的计算模型。
AC 自动机由一个确定有限自动机和一个寄存器组成，能够接受输入字符
串并输出相应的字符串。
它广泛应用于自然语言处理、图像处理、数据压缩等领域。
二、AC 自动机的工作原理
AC 自动机的工作原理可以分为两个主要部分：确定有限自动机和寄
存器。
确定有限自动机负责接受输入字符串，并根据预先定义的规则输出对应的字符串。
寄存器则用于存储自动机当前的状态，以便在处理下一个输入时能够正确地更新输出。
三、AC 自动机的应用领域
1.自然语言处理：AC 自动机在自然语言处理领域有着广泛的应用，
例如在文本生成、机器翻译、情感分析等方面发挥着重要作用。
2.图像处理：AC 自动机可以用于图像的压缩和特征提取，从而在图
像识别、目标检测等任务中提高性能。
3.数据压缩：AC 自动机可以学习数据中的统计特性，并用于压缩和解压缩数据，提高数据传输和存储的效率。
四、AC 自动机的发展前景
随着人工智能、大数据等领域的快速发展，AC 自动机的应用前景十分广阔。
Aho-Corasick算法2018-03-15 10:25:02在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，⽤于在输⼊的⼀串字符串中匹配有限组“字典”中的⼦串。
它与普通字符串匹配的不同点在于同时与所有字典串进⾏匹配。
算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。
AC⾃动机主要依靠构造⼀个有限状态机（类似于在⼀个trie树中添加失配指针）来实现。
这些额外的失配指针允许在查找字符串失败时进⾏回退（例如设Trie树的单词cat匹配失败，但是在Trie树中存在另⼀个单词cart，失配指针就会指向前缀ca），转向某前缀的其他分⽀，免于重复匹配前缀，提⾼算法效率。
当⼀个字典串集合是已知的(例如⼀个计算机病毒库), 就可以以离线⽅式先将⾃动机求出并储存以供⽇后使⽤，在这种情况下，算法的时间复杂度为输⼊字符串长度和匹配数量之和。
UNIX系统中的⼀个命令fgrep就是以AC⾃动机算法作为基础实现的。
⼀、⾃动机⾃动机是计算理论的⼀个概念，其实是⼀张“图”，每个点是⼀个“状态”，⽽边则是状态之间的转移，根据条件能指导从⼀个状态⾛向另⼀个状态。
很多字符串匹配算法都是基于⾃动机模型的，⽐如被⼴泛使⽤的正则表达式。
⼆、AC⾃动机AC⾃动机可以看成是对KMP算法的推⼴，KMP算法是⼀种单模字符串匹配算法，AC⾃动机是多模字符串匹配算法，可以⼀次对多个pattern进⾏匹配。
AC⾃动机的建⽴流程也很简单，主要分为以下⼏步：1.建Trie树2.在Trie树上建⽴失配指针，成为AC⾃动机3.⾃动机上匹配字符串下⾯以模式串he/ she/ his /hers为例，待检测⽂本为“ushers”。
1、建⽴Trie树建⽴Trie树可以说是⾮常模板了。
class TrieNode {TrieNode[] children;TrieNode fail;boolean isWord;TrieNode() {children = new TrieNode[26];fail = null;isWord = false;}}TrieNode root;void bulidTrie(String[] patterns) {root = new TrieNode();for (String pattern : patterns) {TrieNode cur = root;for (int i = 0; i < pattern.length(); i++) {if (cur.children[pattern.charAt(i) - 'a'] == null)cur.children[pattern.charAt(i) - 'a'] = new TrieNode();cur = cur.children[pattern.charAt(i) - 'a'];}cur.isWord = true;}}2、建⽴失配指针AC⾃动机的核⼼就是建⽴失配指针，其思路和KMP算法⾮常类似，在KMP中如果⽂本的text[i...j] 和 pattern[0...j - i]在text[j]出失配，KMP采取的思路是计算pattern[0...j - i - 1]的最长公共前后缀，然后将pattern向后滑动数位，从最长公共前后缀之后继续⽐较，如果依然失配，则重复上述的流程，直到到⾸位，如果依然失配，则text下移。
⾃动机⼊门——AC⾃动机AC ⾃动机1 算法简介AC ⾃动机是⼀个以 Trie 为基础结合 KMP 的思想建⽴的。
在 AC ⾃动机中，每⼀个状态代表着某个模式串的前缀，⽽整个 DFA 的结构其实是所有模式串的Trie 树。
⽽ AC ⾃动机可以处理这样⼀个问题：多模式匹配。
即给你若⼲个模式串和⼀个主串，要求我们对每⼀个字符串和主串进⾏匹配。
我们肯定不能做多次 KMP，所以我们有了 AC ⾃动机。
2 算法讲解2.1 状态设计struct node{int ch[26],end,fail;};其中，ch 数组是 Trie 树的指针，end 是判断这个状态为多少串的节点，fail 指针是后缀链接，指向最长真后缀对应的状态。
⽐如这个动图（其中的黄线是后缀链接）：其中 2 节点的指针画错了，应该是指向 0。
2.2 插⼊因为⾃⾝结构就是 Trie 的结构，所以 AC ⾃动机的插⼊和 Trie 树的插⼊是⼀模⼀样的。
代码：inline void insert(char *s){int now=0,len=strlen(s);for(int i=0;i<len;i++){int k=s[i]-'a';if(!p[now].ch[k]) p[now].ch[k]=++tot;now=p[now].ch[k];}p[now].end++;}2.3 建⽴在这⾥，我们需要建⽴ AC ⾃动机，Trie 树已经建好了，我们的⽬的是构建失配指针 fail 。
暴⼒构建的话就是取其⽗节点，然后不断跳 fail ，直到调到⼀个状态，它有⼀条有相同字符的出边。
但是这样时间复杂度不优，怎样优化？我们先上代码：inline void build(){queue<int> q;for(int i=0;i<26;i++) if(p[0].ch[i]) q.push(p[0].ch[i]);while(q.size()){int top=q.front();q.pop();for(int i=0;i<26;i++){if(p[top].ch[i]) p[p[top].ch[i]].fail=p[p[top].fail].ch[i],q.push(p[top].ch[i]);else p[top].ch[i]=p[p[top].fail].ch[i];}}}这⾥我们通过对跳 fail 的路径进⾏压缩，如果⼦节点存在，那就好说，我们把 fail 直接连过来就可以，但是如果不存在，我们就采⽤路径压缩，把其 fail 的⼦节点连过来，这样就完成了路径压缩。
在C语言中，在字符串中查找某个字符的最快算法是一个常见的问题。
在本文中，我们将讨论一些常用的算法和优化方法，以及它们在查找字符串中某个字符时的效率。
1. 简单线性查找算法最简单的方法是使用线性查找算法，遍历整个字符串，逐个比较字符，直到找到目标字符或到达字符串末尾。
这种方法的时间复杂度为O(n)，其中n为字符串的长度。
2. 使用标准库函数C语言提供了一些标准库函数来处理字符串操作，比如strchr()函数。
这些函数由经验丰富的程序员编写，并经过了优化，通常比手动编写的算法更快。
strchr()函数可以在字符串中查找指定字符的第一次出现的位置，其时间复杂度为O(n)。
3. 优化的线性查找算法在实际应用中，可以对线性查找算法进行一些优化，以提高效率。
使用循环展开、局部性优化等技术可以减少循环迭代和内存访问次数，从而加快查找速度。
可以使用一些技巧，比如将目标字符作为一个整数进行比较，以减少字符比较的时间。
4. 二分查找算法如果字符串是有序的，可以使用二分查找算法来加快查找的速度。
这种算法的时间复杂度为O(log n)，其中n为字符串的长度。
然而，要使用二分查找算法，需要先对字符串进行排序，这会带来额外的时间和空间开销。
5. 哈希表哈希表是一种常见的数据结构，可以在O(1)的时间复杂度内进行查找操作。
可以将字符串中的每个字符映射到一个哈希表中，然后直接查找目标字符是否在哈希表中。
然而，哈希表需要额外的空间来存储映射关系，并且在处理冲突时需要解决哈希碰撞的问题。
6. Boyer-Moore算法Boyer-Moore算法是一种高效的字符串查找算法，它利用了字符比较的位置信息和坏字符规则，可以在最坏情况下达到O(n/m)的时间复杂度，其中n为字符串的长度，m为目标字符串的长度。
这使得Boyer-Moore算法成为一种常用的字符串查找算法。
7. 总结在C语言中，在字符串中查找某个字符的最快算法取决于字符串的特性、目标字符的特性以及对时间和空间的需求。
AC算法学习笔记1、算法流程图（1） void Init()此函数是初始化函数，⽤来给fail数组和goto数组初始化值。
（2） void GotoFunction(string x)这个函数的作⽤是⽣成有限⾃动机状态转移图。
(3) void FailFunction(int target,int k)这是fail函数，核⼼内容是求出每个状态的fail值。
(4) void UpdateOutput()这是update输出函数。
其作⽤是更新每个状态的输出值。
（5）void Check(string x)这个是check函数，其作⽤是判断改状态下output函数是否有输出，如果有输出就输出相应状态下的字符串。
并且决定该状态接受输⼊之后的去向，如果fail，则调⽤该状态的fail 函数来决定去向。
（6）int main()主函数，整个过程的⼊⼝。
2、⾃动机所定义的数据结构及其功能（1） int Goto[M][26];goto数组是状态机状态的载体，内部存储着本次实验的全部状态。
起始状态为0，之后每获得⼀个有效输⼊就⽣成⼀个新的状态。
但是在⽣成状态之前要进⾏检验，看是否已经存在本次状态。
（2） int Fail[M];fail数组存储的是该状态获得输⼊后，如果结果为fail之后的转向状态。
（3） string Output[M];output数组是⼀个字符串数组，存储的是以该状态为终结状态的字符串。
当然，字符串不唯⼀，AC算法的核⼼任务之⼀就是找到每个状态为终结状态时候的全部输出字符串。
（4） string Depth[M];depth数组⽤来标⽰该状态在第⼏层。
我们在此次实验中将goto函数创建的状态看作⼀个树，因此必然需要⼀个数组来指明树中的节点所在的层数。
3、转向函数、失效函数、输出函数的构建过程（1）转向函数我们⾸先来看其伪代码：结合伪代码和刚才的函数流程图，我们可以看出转向函数⾸先对数组进⾏初始化。
第一章1、将编译程序分成若干个“遍”是为了。
b．使程序的结构更加清晰2、构造编译程序应掌握。
a．源程序b．目标语言c．编译方法3、变量应当。
c．既持有左值又持有右值4、编译程序绝大多数时间花在上。
d．管理表格5、不可能是目标代码。
d．中间代码6、使用可以定义一个程序的意义。
a．语义规则7、词法分析器的输入是。
b．源程序8、中间代码生成时所遵循的是- 。
c．语义规则9、编译程序是对。
d．高级语言的翻译10、语法分析应遵循。
c．构词规则二、多项选择题1、编译程序各阶段的工作都涉及到。
b．表格管理c．出错处理2、编译程序工作时，通常有阶段。
a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序。
2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。
3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。
4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题1、文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c. x n yx n(n≥0)d. x*yx*2、文法G描述的语言L(G)是指。
a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)}d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。
a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。
a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。
自动机原理
自动机原理是计算机科学中的一个重要概念，它是指一种能够自动执行特定任务的机器或程序。
自动机原理在计算机科学中有着广泛的应用，包括编译器、操作系统、网络协议等领域。
自动机原理的核心概念是状态和转移。
一个自动机可以被看作是一个状态集合和一组状态之间的转移函数。
在自动机中，每个状态代表着一个特定的状态，而转移函数则描述了在不同状态之间的转移规则。
自动机可以分为有限状态自动机和无限状态自动机两种类型。
有限状态自动机是指状态集合有限的自动机，它们通常用于处理有限的输入序列。
无限状态自动机则是指状态集合无限的自动机，它们通常用于处理无限的输入序列。
在自动机原理中，还有一个重要的概念是确定性自动机和非确定性自动机。
确定性自动机是指在任何给定的状态下，只有一种可能的转移方式。
而非确定性自动机则是指在某些状态下，有多种可能的转移方式。
非确定性自动机通常比确定性自动机更加灵活，但也更加复杂。
自动机原理在计算机科学中有着广泛的应用。
例如，在编译器中，自动机可以用来识别语法错误和生成语法树。
在操作系统中，自动机可以用来管理进程和资源。
在网络协议中，自动机可以用来处理
数据包和建立连接。
自动机原理是计算机科学中的一个重要概念，它可以帮助我们理解计算机系统中的各种自动化过程。
通过深入研究自动机原理，我们可以更好地设计和实现计算机系统，提高计算机系统的效率和可靠性。
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。
