【NOIP模拟】【USACO】 Bovine Genomics

Description

给定两个字符串集合A,B，均包含N个字符串，长度均为M，求一个最短的区间[l,r]，使得不存在字符串\(a\in A,b\in B，\)且\(a[l,r]=b[l,r]\) ，字符串只由ACGT组成，

\(n,m\leq500\)

Input Format

第一行包含N，M，

接下来N行，每行一个长度为M的字符串，描述集合A

最后N行，描述集合B

Output Format

一行表示最短区间的长度

Sample Input

3 8

AATCCCAT

ACTTGCAA

GGTCGCAA

ACTCCCAG

ACTCGCAT

ACTTCCAT

Sample Output

Solution

emmm，可以用字典树\(O(n^3)\)过，

枚举左端点，对于集合A每个字符串构造字典树，

然后查询集合B中每个字符串，更新答案即可

这里有个优化，即如果集合B中存在一个字符串在字典树中完全存在，直接break跳到下个左端点因为答案一定不存在

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#define N 550

using namespace std;

int n,m,tr[N*N][5],Ans,cnt;

char s1[N][N],s2[N][N];

inline int opx(const char &c){

	switch(c){

		case 'A':return 1;break;

		case 'C':return 2;break;

		case 'G':return 3;break;

		default:return 4;break;

	}

}

inline void add(const int &id,const int &l){

	int now=0;

	for(int i=l;i<m;++i){

		int k=opx(s1[id][i]);

		if(!tr[now][k]) tr[now][k]=++cnt;

		now=tr[now][k];

	}

}

inline int Find(const int &id,const int &l){

	int now=0;

	for(int i=l;i<m;++i){

		int k=opx(s2[id][i]);

		if(!tr[now][k]) return i-l+1;

		now=tr[now][k];

	}

	return -1;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i) scanf("%s\n",s1[i]);

	for(int i=1;i<=n;++i) scanf("%s\n",s2[i]);

	Ans=1e9;

	for(int l=0;l<m;++l){

		cnt=0;

		int mx=0;

		memset(tr,0,sizeof(tr));

		for(int i=1;i<=n;++i) add(i,l);

		for(int i=1;i<=n;++i){

			int len=Find(i,l);

			if(len==-1){mx=1e9;break;}

			mx=max(mx,len);

		}

		if(mx==1e9) break;

		Ans=min(Ans,mx);

	}

	printf("%d\n",Ans);

	return 0;

}

巴特西