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

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

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

难度:\(6.0\)

  • 题目描述

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

例如,如果给定的 DNA 序列 \(X\) 和 \(Y\) 分别为 X=AATGCCTAGGCY=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; 

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

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注