1171: 单词匹配
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:6
解决:3
题目描述
为了更好地记住英语单词,我们经常需要比较两个单词的相似程度,有时,我们会说它们很接近!但是如何准确地衡量两个单词的相似程度呢?
我们想了一个办法,举例来说:对于单词CAPILLARY和MARSUPIAL,我们可以这样来比较它们:
CAPILLARY
MARSUPIAL
这样只有一个字母(A)一样,更好的方法是这样对齐:
CAPILLARY
MARSUPIAL
则它们就有两个字母一样了(A和R),但最好的方法是这样:
CAPILLARY
MARSUPIAL
因为这样,它们就有3个字母一样(P,I和L)。这也是这两个单词的最大可能的相似长度了。
根据以上方法,我们可以定义以下一个公式来准确地衡量两个单词的相似程度,假设单词word1和word2,它们的长度分别为length1和length2,它们的最大相似长度为length,则我们用以下分数来表示它们的相似程度:
length * 2
----------------
length1 + length2
这样CAPILLARY和MARSUPIAL这两个单词的相似程度为3*2/(9+9) = 1/3。显然两个单词最大相似程度为1(即两个单词是一样的),最小相似程度为0。
我们想了一个办法,举例来说:对于单词CAPILLARY和MARSUPIAL,我们可以这样来比较它们:
CAPILLARY
MARSUPIAL
这样只有一个字母(A)一样,更好的方法是这样对齐:
CAPILLARY
MARSUPIAL
则它们就有两个字母一样了(A和R),但最好的方法是这样:
CAPILLARY
MARSUPIAL
因为这样,它们就有3个字母一样(P,I和L)。这也是这两个单词的最大可能的相似长度了。
根据以上方法,我们可以定义以下一个公式来准确地衡量两个单词的相似程度,假设单词word1和word2,它们的长度分别为length1和length2,它们的最大相似长度为length,则我们用以下分数来表示它们的相似程度:
length * 2
----------------
length1 + length2
这样CAPILLARY和MARSUPIAL这两个单词的相似程度为3*2/(9+9) = 1/3。显然两个单词最大相似程度为1(即两个单词是一样的),最小相似程度为0。
输入
若干行(最多1000行),每行为一组数据,每组数据是用一个空格隔开的两个单词,每个单词最长100个字符,且都是大写字母。
输出
对于每一行输入,输出一个最简分数,如果是1/1就输出1,如果是0/1就输出0。
样例输入 复制
CAR CART
TURKEY CHICKEN
MONEY POVERTY
样例输出 复制
6/7
4/13
1/3