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

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

题目描述

对于某两个字符串 AA 和 BB,设 AA 的长度为 pp,BB 的长度为 qq,若用以下形式表示他们:

A=a1a2a3…apB=b1b2b3…bqA=a_1a_2a_3\ldots a_p\\B=b_1b_2b_3\ldots b_q

我们说 AA 包含 BB,或者说 BB 是 AA 的子序列,当且仅当存在

1≤i1<i2<⋯<iq≤p1\leq i_1<i_2<\cdots<i_q\leq p

满足

aik=bk for 1≤k≤qa_{i_k}=b_k\text{ for }1\leq k\leq q

你的任务是:给定三个字符串 X,Y,ZX,Y,Z,求 XX 和 YY 的一个公共子序列 WW,使得 WW 包含 ZZ。

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

提示:本题要求找出的 WW 首先是 XX 与 YY 的公共子序列,并且包含 ZZ,然后满足以上这些条件的字符串里面找最长的。

输入格式

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

输出格式

如存在满足条件的 WW,输出 WW 的长度,否则输出 NO SOLUTION。

abclmnopqrsfghituvzwxy
abcdefghijklmnopqrdejkstuvwxyz
fghi
13

样例说明 1

样例中一个最优子序列为 W=abcfghituvwxyW=\texttt{abcfghituvwxy},长度为 1313,并且包含 Z=fghiZ=\texttt{fghi}。

数据规模与约定

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