[Shoi2005] 带限制的最长公共子序列

ID: 2854

传统题

1000ms

128MiB

难度: 10

上传者:

题目描述

对于某两个字符串 $A$ 和 $B$ ，设 $A$ 的长度为 $p$ ， $B$ 的长度为 $q$ ，若用以下形式表示他们：

A=a_1a_2a_3\ldots a_p\\B=b_1b_2b_3\ldots b_q

我们说 $A$ 包含 $B$ ，或者说 $B$ 是 $A$ 的子序列，当且仅当存在

1\leq i_1<i_2<\cdots<i_q\leq p

满足

a_{i_k}=b_k\text{ for }1\leq k\leq q

你的任务是：给定三个字符串 $X,Y,Z$ ，求 $X$ 和 $Y$ 的一个公共子序列 $W$ ，使得 $W$ 包含 $Z$ 。

要求找出最长的这种序列 $W$ 的长度。

提示：本题要求找出的 $W$ 首先是 $X$ 与 $Y$ 的公共子序列，并且包含 $Z$ ，然后满足以上这些条件的字符串里面找最长的。

三行，每行一个字符串，分别表示 $X,Y,Z$ 。

如存在满足条件的 $W$ ，输出 $W$ 的长度，否则输出 NO SOLUTION。

helloworld
hellxebore
xr

样例中答案为 $W=\texttt{hxeor}$ 。

对于 $100\%$ 的数据，非空字符串 $X,Y,Z$ 的长度不超过 $500$ ，由小写字母组成。