P3667 [USACO17OPEN] Bovine Genomics G

题目描述

Farmer John 拥有 $N$ 头有斑点的牛和 $N$ 头没有斑点的牛。他刚刚完成了一门关于牛遗传学的课程，并确信他牛身上的斑点是由牛基因组中的突变引起的。

Farmer John 花费巨资对他的牛进行了基因组测序。每个基因组是一个由字符 A、C、G 和 T 组成的长度为 $M$ 的字符串。当他将牛的基因组排列起来时，会得到如下表格，这里展示的是 $N=3$ 和 $M=8$ 的情况：

位置：   1 2 3 4 5 6 7 8

斑点牛 1：A A T C C C A T  
斑点牛 2：A C T T G C A A  
斑点牛 3：G G T C G C A A  

普通牛 1：A C T C C C A G  
普通牛 2：A C T C G C A T  
普通牛 3：A C T T C C A T  

仔细观察这个表格后，他推测从位置 2 到位置 5 的序列足以解释斑点现象。也就是说，通过仅查看这些位置（即位置 $2 \ldots 5$）的字符，Farmer John 可以预测哪些牛是有斑点的，哪些是没有斑点的。例如，如果他在这些位置看到字符 GTCG，他就知道这头牛一定是有斑点的。

请帮助 Farmer John 找到能够解释斑点现象的最短位置序列的长度。

输入格式

输入的第一行包含 $N$（$1 \leq N \leq 500$）和 $M$（$3 \leq M \leq 500$）。接下来的 $N$ 行每行包含一个长度为 $M$ 的字符串，这些字符串描述了斑点牛的基因组。

最后的 $N$ 行描述了普通牛的基因组。没有任何一头斑点牛的基因组与普通牛的完全相同。

输出格式

请输出能够解释斑点现象的最短位置序列的长度。如果通过查看基因组中这些位置的字符，可以在 Farmer John 的牛群中完美准确地预测斑点性状，那么这个位置序列就解释了斑点现象。

输入输出样例 1

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

4