题目描述

题目译自 PA 2018 Final Podobieństwo genetyczne

我们考虑 DNA 序列，即仅由字符 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 和 $\texttt{T}$ 组成的字符串。我们说字符串 $s$ 是字符串 $s^{\prime}$ 的子序列，如果通过删除 $s^{\prime}$ 中的某些（可能为零个）字符可以得到 $s$。例如，$\texttt{AGG}$ 是 $\texttt{TAGAAG}$ 的子序列，而 $\texttt{AGGA}$ 不是。

对于两个字符串 $s_{1}$ 和 $s_{2}$，我们定义它们的 $m$-相似性为长度为 $m$ 的序列 $w$ 的数量，其中 $w$ 是 $s_{1}$ 的子序列当且仅当 $w$ 也是 $s_{2}$ 的子序列。换句话说，这是长度为 $m$ 的序列中，要么是两个字符串的子序列，要么都不是两个字符串的子序列的序列数量。

对于给定的字符串 $s_{1}$、$s_{2}$ 和数字 $m$，计算 $s_{1}$ 和 $s_{2}$ 的 $m$-相似性。

输入格式

输入由三行组成。

前两行分别是序列 $s_{1}$ 和 $s_{2}$，每个序列包含至少 $1$ 个、最多 $1000000$ 个字符，字符取自集合 $\{\texttt{A}, \texttt{C}, \texttt{G}, \texttt{T}\}$。

第三行包含一个整数 $m$ $(1 \leq m \leq 20)$。

输出格式

输出一个整数：$s_{1}$ 和 $s_{2}$ 的 $m$-相似性。

TCAGG
TAGAAG
2

11

为了计算序列 $\texttt{TCAGG}$ 和 $\texttt{TAGAAG}$ 的 $2$-相似性，需要考虑所有 $4^{2}=16$ 种可能的双字符序列。其中，三个（$\texttt{CA}, \texttt{CG}, \texttt{TC}$）仅是第一个序列的子序列，两个（$\texttt{AA}, \texttt{GA}$）仅是第二个序列的子序列，四个（$\texttt{AG}, \texttt{GG}, \texttt{TA}, \texttt{TG}$）是两个序列的子序列，而其余七个（$\texttt{AC}, \texttt{AT}, \texttt{CC}, \texttt{CT}, \texttt{GC}, \texttt{GT}, \texttt{TT}$）都不是两个序列的子序列。因此，所需的 $2$-相似性为 $4 + 7 = 11$。

T
AG
3

64