P4608 [FJOI2016] All Common Subsequences

A subsequence of a given sequence is obtained by deleting some elements from that sequence. Precisely, given a sequence $X = x_1 x_2 \ldots x_m$, another sequence $Z = z_1 z_2 \ldots z_k$ is a subsequence of $X$ if there exists a strictly increasing index sequence $i_1, i_2, \ldots, i_k$ such that for all $j = 1, 2, \ldots, k$ we have $z_j = x_{i_j}$. For example, the sequence $Z = ``GACT''$ is a subsequence of the sequence $X = ``GCTACT''$, with the corresponding increasing index sequence $1, 4, 5, 6$. Given two sequences $X$ and $Y$, when another sequence $Z$ is a subsequence of both $X$ and $Y$, we call $Z$ a common subsequence of $X$ and $Y$. For example, if $X = ``GCTACT''$ and $Y = ``GATCCT''$, the sequence ``T'' is a common subsequence of $X$ and $Y$, and the sequence ``GACT'' is also a common subsequence of $X$ and $Y$. Note that for any given sequences $X$ and $Y$, the empty sequence is always their common subsequence. The All Common Subsequences problem asks you, given two sequences $X = x_1 x_2 \ldots x_m$ and $Y = y_1 y_2 \ldots y_n$, to find all distinct common subsequences of $X$ and $Y$.

The first line contains two positive integers $m$ and $n$, the lengths of the two input sequences $X$ and $Y$. The next two lines give the input sequences $X = x_1 x_2 \cdots x_m$ and $Y = y_1 y_2 \cdots y_n$, where each element of a sequence is an English letter, uppercase or lowercase. The last line contains a non-negative integer $k$. If $k = 1$, you must output all distinct common subsequences of $X$ and $Y$, and also how many distinct common subsequences $X$ and $Y$ have. If $k = 0$, you must output only how many distinct common subsequences $X$ and $Y$ have.

Output all distinct common subsequences of $X$ and $Y$, or output how many distinct common subsequences $X$ and $Y$ have. When $k = 1$, first output all distinct common subsequences of $X$ and $Y$, one per line, in ascending lexicographic order. Finally, output the number of distinct common subsequences. When $k = 0$, output only the number of distinct common subsequences.

$1 \leq m, n \leq 3010$. The answer can be very large. Translated by ChatGPT 5