YZOJ P2049 [FJOI2013]相似基因序列问题

时间限制：1000MS      内存限制：262144KB

难度：$6.0$

• 题目描述

给定 $2$ 个长度分别为 $m$ 和 $n$ 的 DNA 序列 $X$ 和 $Y$，以及一个长度为 $p$ 的模式子序列 $P$。带有子序列包含约束的最长公共子序列问题就是要找出 $X$ 和 $Y$ 带有包含子序列 $P$ 约束的最长公共子序列的长度。

例如，如果给定的 DNA 序列 $X$ 和 $Y$ 分别为 X=AATGCCTAGGC，Y=CGATCTGGAC，模式子序列 P=GTAC，则子序列 ATCTGGC 是 $X$ 和 $Y$ 的一个无约束的最长公共子序列，而包含 $P$ 为其子序列的最长公共子序列是 GCTAC。

• 输入格式

第一行中给出正整数 $m,n,p$，分别表示给定序列 $X$ 和 $Y$ 以及模式子序列 $P$ 的长度。$m,n,p<300$ 。

接下来的 $3$ 行分别给出序列 $X$ 和 $Y$ 以及模式子序列 $P$ 。

• 输出格式

将计算出的 $X$ 和 $Y$ 带有包含子序列 $P$ 约束的最长公共子序列的长度输出。如果 $X$ 和 $Y$ 不存在包含子序列 $P$ 的公共子序列，则输出 $-1$。

• 样例输入

• 样例输出

 

 

 

---

 

 

 

要是没有 $P$ 串，直接在 $X, Y$ 的序列自动机上跑匹配即可。

考虑有 $P$ 串的限制，可以构造一个新自动机：

对于 $0 \leq i < p$ ， next[i][ P[i+1] ] = i+1, next[i][ (other) ] = i; 

对于 $i = p$ ， next[i][ (all) ] = i; 

然后三个自动机跑最大匹配即可。