P14095 [ICPC 2023 Seoul R] Tandem Copy

串联复制是一种对 DNA 序列的操作，在该操作中，一段连续的一个或多个核苷酸序列会被重复一次，并且这些重复直接紧挨在原序列后面。换句话说，串联复制操作会将一段连续的核苷酸序列复制，并将该复制品粘贴在被复制序列的后面。例如，$\texttt{ATCATCG}$ 是在 $\texttt{ATCG}$ 中对 $\texttt{ATC}$ 进行串联复制得到的。此外，我们还可以继续对得到的序列 $\texttt{ATCATCG}$ 进行一次串联复制，得到 $\texttt{ATCATTCG}$。下面的例子演示了从 $\texttt{ATCG}$ 开始进行一系列串联复制的过程，其中每一步下划线标记的是被复制的序列。 $$\texttt{\underline{ATC}G}\Rightarrow\texttt{ATCA\underline{T}CG}\Rightarrow\texttt{\underline{AT}CATTCG}\Rightarrow\texttt{ATATC\underline{ATT}CG}\Rightarrow\dots$$ 我们说，$\texttt{ATCG}$ 能够通过串联复制产生所有这些序列。显然，$\texttt{ATCG}$ 可以通过每一步选择不同部分来进行串联复制，因此可以产生不同的序列。此外，原则上，$\texttt{ATCG}$ 可以通过不断串联复制产生无限多个序列。 通常，复制较长的部分代价更高。例如， $$\texttt{\underline{ATC}G}\Rightarrow\texttt{ATCATCG}$$ 是将三个核苷酸进行串联复制，因此比下面只复制一个核苷酸的操作更昂贵： $$\texttt{ATCA\underline{T}CG}\Rightarrow\texttt{ATCATTCG}$$ 也就是说，每一步被复制部分的长度对于确定串联复制的代价至关重要。 由于对单个核苷酸进行串联复制很容易，因此实验室往往以相邻的两个核苷酸总是不相同的方式存储序列，以节省存储空间。例如，因为 $\texttt{ATTTG}$ 可以通过从 $\texttt{ATG}$ 串联复制两个 $\texttt{T}$ 得到，所以实验室更愿意只保存更短的序列 $\texttt{ATG}$，而不是 $\texttt{ATTTG}$。 由于最近经费削减，实验室现在每次串联复制操作最多只允许复制两个核苷酸，也就是说，每一步复制的长度最多为 2。另一方面，实验室可以任意多次执行串联复制操作。例如，给定序列 $\texttt{ABCD}$，我们可以对 $\texttt{B}$ 进行串联复制，得到 $\texttt{ABBCD}$，或者对 $\texttt{BC}$ 进行复制，得到 $\texttt{ABCBCD}$。但是我们不能对连续的 $\texttt{ABC}$ 进行串联复制，因为其长度大于 2。 现在给定一个原串 $s$ 和目标串 $t$，你的任务是统计 $s$ 的所有合法子串 $s'$ 的数量，使得可以通过若干次串联复制操作，从 $s'$ 得到某个字符串 $x$，其中 $x$ 包含 $t$ 作为子串。注意，原串 $s$ 中保证任意两个相邻的核苷酸都不同，而目标串 $t$ 的相邻核苷酸可以相同。例如，$\texttt{CCA}$ 或 $\texttt{ATTGC}$ 不能作为原串，但可以作为目标串。 举个例子，$s=\texttt{ACATGCAT}$，$t=\texttt{CCACATTT}$，我们取 $s$ 的一个子串 $s'=\texttt{CATGC}$ ，然后进行如下串联复制操作： $$s'=\texttt{\underline{C}ATGC}\Rightarrow\texttt{C\underline{CA}TGC}\Rightarrow\texttt{CCACA\underline{T}GC}\Rightarrow\texttt{CCACAT\underline{T}GC}\Rightarrow\texttt{CCACATTTGC}$$ 最终得到的序列包含目标串 $t$。 另一个子串的例子：对 $s'=\texttt{CAT}$， $$s'=\texttt{\underline{CA}T}\Rightarrow\texttt{\underline{C}ACAT}\Rightarrow\texttt{CCACA\underline{T}}\Rightarrow\texttt{CCACA\underline{T}T}\Rightarrow\texttt{CCACATTT}=t$$ 可以看出，可以通过一系列串联复制操作从 $\texttt{CAT}$ 得到目标串。 很容易验证，$s$ 的合法子串总数为 $14$。注意，$s$ 中的第一个 $\texttt{CAT}$ 和第二个 $\texttt{CAT}$ 被视为不同的合法子串，因此你需要将 $s$ 的所有子串全部考虑，并分别统计。 另一个例子：当 $s=\texttt{AB}$，$t=\texttt{BA}$ 时，可以取子串 $\texttt{AB}$，然后对 $\texttt{AB}$ 进行一次串联复制，得到 $\texttt{ABAB}$，其中包含 $\texttt{BA}$ 作为子串。$s$ 的其他子串都无法通过串联复制产生包含 $\texttt{BA}$ 的序列，因此合法子串的数量为 $1$。 给定原串 $s$ 和目标串 $t$，其中 $s$ 保证没有两个相邻字符相同，请编写程序输出 $s$ 的所有合法子串 $s'$ 的数量。若对 $s'$ 进行若干次串联复制（每次复制长度最大为 2），能够生成包含目标串 $t$ 的某个字符串，则 $s'$ 为合法子串。

你的程序需从标准输入读取数据。输入包含两行。第一行为原串 $s$，第二行为目标串 $t$。每行均为由大写字母 `A` 到 `Z` 组成，且 $1\leq |s|,|t| \leq 2\times 10^4$。

你的程序需输出一行，该行为一个整数，表示通过若干次串联复制能够得到包含目标串 $t$ 的所有合法子串数量。

由 ChatGPT 5 翻译