P4584 [FJOI2015] LCS with Substring Inclusion Constraints

The longest common subsequence problem with substring inclusion constraints can be stated as follows. Given two sequences $X$ and $Y$ of lengths $n$ and $m$, respectively, and a set $S$ of substring inclusion constraints. There are $k$ strings in $S$, $S=\{S_1,S_2,…,S_k\}$, where the length of string $S_i$ is $l_i$, $1 \le i \le k$. The problem is to find a longest common subsequence of $X$ and $Y$ that contains every string in the constraint set $S$ as its substring. For example, if the given sequences are $X = \texttt{actaagacct}$ and $Y = \texttt{gacctacctc}$, and the constraint set is $S=\{\texttt{ata}, \texttt{tact}\}$, then the subsequence actacct is an unconstrained LCS of $X$ and $Y$, while a longest common subsequence that contains all strings in $S$ as substrings is atact. In this problem, please pay special attention to the difference between substring and subsequence. The substring of a string $T=t_1…t_n$ is a string of the form $T$’$=t_1+i…t_m+i$, where $0 \le i$, $m+i \le n$. For example, if $T=\texttt{abcdefg}$, then bcd is a substring of $T$, while bce is a subsequence of $T$ but not a substring of $T$. Design an algorithm to find a longest common subsequence of the given sequences $X$ and $Y$ that satisfies the substring inclusion constraints $S$.

- The first line contains positive integers $n$, $m$, $k$, with $m < 300$, $n < 300$, $k < 6$. Here $n$ and $m$ are the lengths of the given sequences $X$ and $Y$, respectively. The value $k$ is the number of strings in the constraint set $S$. - The second line contains $k$ integers $l_i$, with $0 \le l_i \le 300$, $1 \le i \le k$, which are the lengths of the $k$ strings in the constraint set $S$. - The third and fourth lines give the sequences $X$ and $Y$. - The next $k$ lines each contain one string $S_i$.

Output the length of a longest common subsequence of $X$ and $Y$ that satisfies the substring inclusion constraints $S$.

The strings contain only uppercase and lowercase letters. Translated by ChatGPT 5