问题 E: [Usaco2017 Open]Bovine Genomics
时间限制: 1 Sec 内存限制: 128 MB
提交: 214 解决: 50
题目描述
Farmer John owns Ncows with spots and N cows without spots. Having just completed a course in bovine
genetics, he is convinced that the spots on his cows are caused by mutations in the bovine genome.A
t great expense, Farmer John sequences the genomes of his cows. Each genome is a string of length Mb
uilt from the four characters A, C, G, and T. When he lines up the genomes of his cows, he gets a ta
ble like the following, shown here for N=3 and M=8:
Positions: 1 2 3 4 5 6 7 8
Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C T T G C A A
Spotty Cow 3: G G T C G C A A
Plain Cow 1: A C T C C C A G
Plain Cow 2: A C T C G C A T
Plain Cow 3: A C T T C C A T
Looking carefully at this table, he surmises that the sequence from position 2 through position 5 is
sufficient to explain spottiness. That is, by looking at the characters in just these these positio
ns (that is, positions 2…5), Farmer John can predict which of his cows are spotty and which are not
. For example, if he sees the characters GTCG in these locations, he knows the cow must be spotty.Pl
ease help FJ find the length of the shortest sequence of positions that can explain spottiness.
给定n个A串和n个B串，长度均为m，求一个最短的区间[l,r]
使得不存在一个A串a和一个B串b，使得a[l,r]=b[l,r]
n,m≤500
输入
The first line of input contains N(1≤N≤500) and M (3≤M≤500). The next N lines each contain a str
ing of M characters; these describe the genomes of the spotty cows. The final Nlines describe the ge
nomes of the plain cows. No spotty cow has the same exact genome as a plain cow.
输出
Please print the length of the shortest sequence of positions that is sufficient to explain spottine
ss. A sequence of positions explains spottiness if the spottiness trait can be predicted with perfec
t accuracy among Farmer John’s population of cows by looking at just those locations in the genome.
样例输入
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
样例输出
4
从一节点开跑
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#define MAXN 250005
//#define LL long long
using namespace std;
struct Trie
{//nt dfn;//nt dep;Trie *ch[27];
}node[MAXN],*root;
int n,t,sz,ll,pp;
char s1[505][505],s2[505][505];
inline Trie* newnode()
{sz++;return &node[sz];
}
inline void insert(char *s)
{Trie *now=root; int len=strlen(s);for(int i=0;i<len;i++){if(now->ch[s[i]-'A']==NULL)now->ch[s[i]-'A']=newnode();now=now->ch[s[i]-'A'];}
}
inline int query(char *s,Trie*rt)
{int len=strlen(s);Trie *cur=rt;for(int i=0;i<len;i++){int k=s[i]-'A'; if(!cur->ch[k]){ll=max(ll,i+1);return 0;}cur=cur->ch[k];}pp=1;return 1;
}
inline void init()
{sz=0;memset(node,0,sizeof(node));root=newnode(); ll=0; pp=0;
}
inline int ttt()
{//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);// freopen("link.in","r",stdin);freopen("link.out","w",stdout);int ans=505,len;scanf("%d%d",&n,&len);for(int i=1;i<=n;i++)scanf("%s",s1[i]);for(int i=1;i<=n;i++)scanf("%s",s2[i]); int mid,l=2,r=len; for(int k=0;k<len;k++){init();for(int i=1;i<=n;i++) insert(s1[i]+k);for(int j=1;j<=n;j++)query(s2[j]+k,root); if(pp)break;ans=min(ans,ll); }cout<<ans<<endl;return 0; }
int ddd=ttt();
int main()
{;}