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\)。
-
样例输入
1 2 3 4 |
11 10 4 AATGCCTAGGC CGATCTGGAC GTAC |
-
样例输出
1 |
5 |
要是没有 \(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;
然后三个自动机跑最大匹配即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> inline int _max(const int&a,const int&b) { return (a>b?a:b); } char xs[305],ys[305],ps[305]; #define CHARSET 26 int xpos[305][30],ypos[305][30],ppos[305][30]; inline void build(int ls,char s[],int pos[][30]) { for(register int i=ls;i>=1;i--) { for(register int j=0;j<CHARSET;j++) pos[i-1][j]=pos[i][j]; pos[i-1][s[i]-'A']=i; } } bool vis[305][305][305]; int f[305][305][305]; int P; int DFS(register int x,register int y,register int p) { if(vis[x][y][p]) return f[x][y][p]; vis[x][y][p]=true; register int ans=(p==P?0:INT_MIN); for(register int j=0;j<CHARSET;j++) if(xpos[x][j] && ypos[y][j] && ppos[p][j]) ans=_max(ans,DFS(xpos[x][j],ypos[y][j],ppos[p][j])); return (f[x][y][p]=ans+1); } int main() { int N,M,P;scanf("%d%d%d",&N,&M,&P); ::P=P; scanf("%s",&xs[1]),scanf("%s",&ys[1]),scanf("%s",&ps[1]); build(N,xs,xpos),build(M,ys,ypos); for(register int i=P;i>=0;i--) { for(register int j=0;j<CHARSET;j++) ppos[i][j]=i; if(i<P) ppos[i][ps[i+1]-'A']=i+1; } DFS(0,0,0); printf("%d\n",(f[0][0][0]-1>0 ? f[0][0][0]-1 : -1)); return 0; } |