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

4

Solution

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

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

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

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

Code

#include 
    
     #include 
     
      #include 
      
       #define N 550using 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