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; 

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