Bovine Genomics (Gold)#10527
Farmer John owns spotty cows and 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.
At great expense, Farmer John sequences the genomes of all his cows. Each genome is a string of length consisting of the four characters A, C, G, and . When he lines up the genomes of his cows, he obtains a table 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 TLooking carefully at this table, he notices that the sequence of positions from through is sufficient to distinguish the spotty cows from the plain cows. In other words, by looking only at the characters in these positions (that is, positions ), Farmer John can determine with certainty whether a cow is spotty or plain. For example, if he sees the sequence in these positions, he knows that the cow must be spotty.
Please help FJ find the length of the shortest contiguous sequence of positions that can distinguish the spotty cows from the plain cows.
The first line contains n~(1 \le n \le 500) and m~(3 \le m \le 500). The next lines each contain a string of characters, describing the genomes of the spotty cows. The final lines describe the genomes of the plain cows. No spotty cow has the same exact genome as any plain cow.
Print the length of the shortest contiguous sequence of positions that is sufficient to distinguish the spotty cows from the plain cows. A sequence of positions distinguishes the spotty cows from the plain cows if the spottiness trait can be predicted with perfect accuracy for all of Farmer John's cows by looking only at those positions in their genomes.
Beispiel 1