logo AlgoBeat OnlineJudge
登录 注册

#216076. [CSPro 33] 相似度计算

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

洛谷的测试数据仅供民间交流使用,非官方测试数据。官方评测链接:https://www.cspro.org/

两个集合的 Jaccard 相似度定义为:

即交集的大小除以并集的大小。当集合 完全相同时, 取得最大值;当二者交集为空时, 取得最小值。


除了进行简单的词频统计,小 P 还希望使用 Jaccard 相似度来评估两篇文章的相似性。具体来说,每篇文章均由若干个英文单词组成,且英文单词仅包含“大小写英文字母”。对于给定的两篇文章,小 P 首先需要提取出两者的单词集合 ,即去掉各自重复的单词。然后计算出:

  • ,即有多少个不同的单词同时出现在两篇文章中;
  • ,即两篇文章一共包含了多少个不同的单词。

最后再将两者相除即可算出相似度。需要注意,在整个计算过程中应当忽略英文字母大小写的区别,比如 the、The 和 THE 三者都应被视作同一个单词。

试编写程序帮助小 P 完成前两步,计算出 ;小 P 将亲自完成最后一步的除法运算。

输入格式

从标准输入读入数据。

输入共三行。

输入的第一行包含两个正整数 ,分别表示两篇文章的单词个数。

第二行包含空格分隔的 个单词,表示第一篇文章;

第三行包含空格分隔的 个单词,表示第二篇文章。

输出格式

输出到标准输出。

输出共两行。

第一行输出一个整数 ,即有多少个不同的单词同时出现在两篇文章中;

第二行输出一个整数 ,即两篇文章一共包含了多少个不同的单词。

样例

样例输入 1

3 2
The tHe thE
the THE

样例输出 1

1
1

样例输入 2

9 7
Par les soirs bleus dete jirai dans les sentiers
PICOTE PAR LES BLES FOULER LHERBE MENUE

样例输出 2

2
13

样例输入 3

15 15
Thou that art now the worlds fresh ornament And only herald to the gaudy spring
Shall I compare thee to a summers day Thou art more lovely and more temperate

样例输出 3

4
24

数据范围与提示

样例 1 解释

样例 2 解释

子任务

  • 的测试数据满足: 且所有字母均为小写;
  • 全部的测试数据满足: 且每个单词最多包含 个字母。