「国家集训队」最长双回文子串-回文自动机

输入长度为 $n$ 的串 $S$ ,求 $S$ 的最长双回文子串 $T$,即可将 $T$ 分为两部分$X$ , $Y$ , ( $∣X∣,∣Y∣ \geq 1$ )且 $X$ 和 $Y$ 都是回文串。

「CF232D」Fence-后缀数组+主席树

给定长度为 $n$ 的整数序列 $h[n]$ ,有 $Q$ 个询问,每次给出 $l_1,r_1$ ,​询问有多少对 $l_2,r_2$ ,满足以下条件:

  1. $r_2 – l_2 = r_1 – l_1$
  2. 区间 $[l_1, r_1]$ 与区间 $[l_2, r_2]$ 没有交集
  3. 对于任意 $i \in [0,r_1 – l_1]$ ,满足 $h[l_1 + i] + h[l_2 + i] = h[l_1] + h[l_2]$

「CTSC2012」熟悉的文章-广义后缀自动机

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想出了一个评定作文 “熟悉程度”的量化指标:$L_0$ .小强首先将作文转化成一个 $01$ 串。之后,小强搜集了各路名家的文章,同样分别转化成 $01$ 串后,整理出一个包含了 $M$ 个 $01$ 串的“ 标准作文库 ”。

小强认为:如果一个 $01$ 串长度不少于 $L$ 且在 标准作文库 中的某个串里出现过(即,它是 标准作文库 的 某个串 的一个 连续子串 ),那么它是“ 熟悉 ”的。对于一篇作文(一个 $01$ 串)A,如果能够把 A 分割成若干段子串,其中“ 熟悉 ” 的子串的 长度总和 不少于 A 总长度的 $90\%$,那么称 A 是 “ 熟悉的文章 ”。 $L_0$ 是能够让 $A$ 成为 “ 熟悉的文章 ” 的 所有 $L$ 的最大值 (如果不存在这样的 $L$ ,那么规定 $L_0 = 0$ )。

「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 序列的个数。

「CF452E」Three strings-后缀数组

给出三个仅由小写字母构成的串 $A, B, C$ ,对于每个 $L \in [1, \min(len_A,len_B,len_C)]$ ,求满足$A[a,a+L-1] = B[b,b+L-1] = C[c,c+L-1]$ 的三元组 $(a,b,c)$ 的数量。

答案对 $1000000007 (10 ^ 9 + 7)$ 取模,字符总数小于 $3\times10^5$。

「JSOI2007」字符加密-后缀数组

喜欢钻研问题的 $JS$ 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。

例如 JSOI07 ,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 ,把它们按照字符串的大小排序:

  • 07JSOI
  • 7JSOI0
  • I07JSO
  • JSOI07
  • OI07JS
  • SOI07J

读出最后一列字符:I0O7SJ,就是加密后的字符串。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

「HNOI2004」L语言-AC自动机

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

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

「BZOJ4278」[ONTAK2015]Tasowanie-后缀数组

给定两个数字串 $A$ 和 $B$ ,通过将 $A$ 和 $B$ 进行二路归并得到一个新的数字串 $T$ ,请找到字典序最小的 $T$ 。

「POI2006」Periods of Words-KMP

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 $P$ 是串 $A$ 的前缀, 当且仅当存在串 $B$ , 使得 $A = PB$. 如果 $P \neq A$ 并且 $P$ 不是一个空串,那么我们说 $P$ 是 $A$ 的一个 $proper$ 前缀. 定义 $Q$ 是 $A$ 的周期, 当且仅当 $Q$ 是 $A$ 的一个 $proper$ 前缀并且 $A$ 是 $QQ$ 的前缀(不一定要是 $proper$ 前缀).

比如串 $abab$ 和 $ababab$ 都是串 $abababa$ 的周期. 串 $A$ 的最大周期就是它最长的一个周期或者是一个空串(当 $A$ 没有周期的时候), 比如说, $ababab$ 的最大周期是 $abab$ . 串 $abc$ 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.

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

可读版题意:

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

Your browser is out-of-date!

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

×