基因序列相似性问题CCR版(KM模式匹配)

【题十五】基因序列相似性问题(dna.cpp/c/pas)

师大附中?陈超锐

内存限制256MB? 时间限制1s

?

【题目背景】

最长公共子序列问题是生物信息学中序列比对问题的一个特例。这类问题在分子生物学和模式识别中有广泛应用。其中最主要的应用是测量基因序列的相似性。在演化分子生物学的研究中发现，某个重要的DNA序列片段常出现在不同的物种中。在测量基因序列的相似性时，如果需要特别关一个具体的DNA序列片段，就要考察带有子串包含约束的最长公共子序列问题。

【题目描述】
这个问题可以具体表述如下：给定2个长度分别为m和n的DNA序列X和Y，以及一个长度为p的模式子串P．带有子序列包含约束的最长公共子序列问题就是要找出x和Y的不包含P为其子串的最长公共子序列。
　　例如，如果给定的DNA序列x和Y分别为X=AATGCCTAGGC，Y=CGATCTGGAC，模式子序列P=TGGC，则子序列ATCTGGC是X和Y的一个无约束的最长公共子序列，而不包含P为其子串的最长公共子序列是ATCTGC(可能不唯一)。
编程任务：找出给定序列X和Y带有不包含子串P约束的最长公共子序列。

【输入格式】(dna.in)

文件的第1行中给出正整数m,n,p，分别表示给定序列X和Y以及模式子串P的长度。m<200,n<200,p<200。接下来的3行分别给出序列X和Y以及模式子串P。

【输出格式】(dna.out)

将计算出的X和Y带有不包含子串P约束的最长公共子序列的长度输出，不存在则长度为0。

【样例输入】

11 10 4

AATGCCTAGGC

CGATCTGGAC

TGGC

【样例输出】

6

【数据范围】

对于20%的数据：0<n,m,p<=10;

对于60%的数据，0<n,p<=100

对于100%的数据：0<n,p<=200；

一年多没写KMP了各种伤不起……

仅仅是隐约记得pre的含义是(将1-i的后半段与1-pre[i]匹配)

结点好不容易知道std的标程大概咋回事了居然WA

原因是k必须在最内层循环……(想想也是f[i][j]k]更新的f[i+1][j+1][t],t有可能在k前面)

f[i][j][k]自然表示a匹配到i,b匹配到j时,最后几位与模式串p匹配最后(前面不影响)匹配到第k位时的最大匹配长度

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<functional>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<=n;i++)
#define MAXN (200+10)
char a[MAXN],b[MAXN],c[MAXN];
int n,p;
int f[MAXN][MAXN][MAXN];
int pre[MAXN];
void kmp()
{
	pre[0]=-1,pre[1]=0;
	int j=0;
	Fork(i,2,p+1) 
	{
		if(j^-1&&c[i]^c[j+1]) j=pre[j];
		pre[i]=++j; 
	}
}
int main()
{
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	scanf("%d%d%d",&n,&m,&p);
	scanf("%s%s%s",a+1,b+1,c+1);
	kmp();	
	memset(f,128,sizeof(f));
	f[0][0][0]=0;
	Fork(i,n)
		Fork(j,m)
			Fork(k,p-1)
			{
				if (!f[i][j][k]&&k) continue;
				if (i<n) f[i+1][j][k]=max(f[i+1][j][k],f[i][j][k]);
				if (j<m) f[i][j+1][k]=max(f[i][j+1][k],f[i][j][k]);
				if (i<n&&j<m&&a[i+1]==b[j+1])
				{
					int t=k;
					while (t^-1&&c[t+1]^a[i+1]) t=pre[t];
					++t;
					f[i+1][j+1][t]=max(f[i+1][j+1][t],f[i][j][k]+1); 
				}
			}
	int ans=0;
	Rep(i,p-1) ans=max(ans,f[n][m][i]);
	cout<<ans<<endl;
	return 0;
}