题解

题面描述

给定$n$个字符串集合，每个集合$S_i$包含$A_i$个字符串。对于每个集合$S_i$，需要找到另一个集合$S_j$（$j \neq i$），使得$S_i$与$S_j$的交集中字符串的数量最多。如果存在多个满足条件的$S_j$，则选择序号最小的那个。如果$S_i$与任何其他集合的交集都为空，则选择序号最小的$S_j$（$j \neq i$），并输出交集的字符串数量为$0$。

思路

1. 数据结构选择：

题目内容

两个集合$A$和$B$的交集指的是，所有属于集合$A$目属于集合$B$的元素所组成的集合。

给定$n$个字符串集合，每个字符串集合$si(1 <=i<=n)$中字符串数目为$Ai$，对每个字符串集合$Si$，请找到序号最小的$j(j≠i)$满足$Sj$与$Si$的交集中字符串个数最多，并输出与交集中的字符串个数。如果$Si$与任何其他集合的交集都为空。

我们认为交集个数全部为$0$，输出其他集合中序号最小的即可。例如样例$1$中S4输出的是$1\ 0$；例如$S1$与其他集合交集全为空，则输出$2\ 0$.

输入描述

第一行一个数$n$，表示字符串集合的数量;从第二行开始，共分为$n$个部分:

第$i$部分第一行一个数$Ai$，表示该字符串集合$Si$中的字符串数量;下接$Ai$行，代表$Si$内的所有字符串。

约束:

$1、1 <n <=100$

$2、0 <Ai <= 100$

$3$、单个字符串的长度为$len, 0 < len <= 100$

字符串中只包含大小写字母与数字

输出描述

输出共$n$行，每行两个数字$j$和$x$，分隔符为$1$个空格；$j$代表与$Si$交集中字符串个数最多的是$Sj$；$x$代表$Si$与$Sj$交集中的字符串个数。

样例1

输入

4
3
123
456
789
3
234
345
4567
5
123
456
789
0123
4567
1
6789

输出

3 3
3 1
1 3
1 0

说明

1.对于字符串集合$S1${"$123$","$456$","$789$}，与$S3$的交集中字符串个数最多，它俩的交集中有$3$个字符串，即{"$123$","$456$","$789$"}

$2$.对于字符串集合$S2${"$234$","$345$'',"$4567$"}，与$S3$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$4567$"}

$3$.对于字符串集合$S3${"$123$","$456$","$789$","$0123$","$4567$”}，与其$S1$的交集中字符串个数最多，它俩的交集中有$3$个字符串，即{"$123$","$456$","$789$"}

$4$.对于字符串集合$S4${"$6789$"}，与$S1、S2、S3$的交集全部为空，序号最小的是$S1$,输出$1\ 0$。

样例2

输入

3
2
123
678
3
728
8888
1000
2
123
728

输出

3 1
3 1
1 1

说明

$1$.对于字符串集合$S1${"$123$","$678$"}，与$S3$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$123$"}

$2$.对于字符串集合$S2$ {"$728$","$8888$","$1000$"}，与$S3$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$728$"}

$3$.对于字符串集合$S3${"$123$","$728$"}，与$S1$的交集中字符串个数最多，它俩的交集中有$1$个字符串，即{"$123$"}