「CF86C」Genetic engineering-AC自动机+dp

我们定义一个 DNA 序列为仅有 ATCG 四个字母的字符串。

给出 $m(1 \le m \le 10)$ 个 DNA 序列模式串 $s_i$,每个长度均不超过 $10$ ,我们定义一个 DNA 序列 $w$ 是好的,当且仅当对于 $w$ 的每一个位置 $i$ ,都存在至少一个模式串 $s_j$ , 使得 $w[l…r] = s_j$( $w[l…r]$ 表示一个原字符串的一个子串) , 其中 $1 \le l \le i \le r \le |w|$( $|w|$ 为 DNA序列 $w$ 的长度) 。

请你计算出所有长度为 $n(1 \le n \le 1000)$ 的好的 DNA 序列的个数。

「HNOI2004」L语言-AC自动机

一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的,是指如果文章 $T$ 可以被分成若干部分,且每一个部分都是字典 $D$ 中的单词。

给定一个字典 $D$ ,你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。并给出其在字典 $D$ 下能够被理解的最长前缀的位置。

「JSOI2007」文本生成器-AC自动机+dp

可读版题意:

给定 $n$ 个仅包含大写字母的模板串,求所有的长度为 $M$ 且仅包含大写字母的不同字符串中,有多少个包含至少一个模板串。答案对 $10007$ 取模。

「POI2000」病毒-AC自动机

二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。

AC自动机学习笔记

Aho–Corasick算法,常叫做AC自动机。是一种字符串多模式串匹配算法。能在线性时间内完成多个模式串对一个查询串的匹配。

能自动AC哦。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×