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

给定长度为 $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]$

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

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

我们定义一个 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 序列的个数。

给出三个仅由小写字母构成的串 $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 \times 10^5$。

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

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

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

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

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

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

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

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 $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$ 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.

可读版题意：

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

对于一个 $0/1$ 字符串，如果将这个字符串 $0$ 和 $1$ 取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的， $1001$ 就不是。

现在给出一个长度为 $n$ 的 $0/1$ 字符串，求它有多少个子串是反对称的。

可读版题意：

给定 $n$ 个字符串，第 $i$ 个字符串的长度为 $M_i$ ，求每个字符串在所有字符串中出现的次数。

数据范围：$n \leq 100,\ M = \sum M_i \leq 10^6$.

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

简单版题意：

给定一个长度为 $n$ 的字符串，和一个长度为 $n$ 的数列 ${a_n}$ ，求对于 $r$ 从 $0$ 到 $n-1$ ，所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。（ $a_i$ 可以为负数）

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。当这两个子串中只要有一个取得位置不同时，两个方案不同。