7-44 基于词频的文件相似度 (30 分)
实现一种简单原始的文件相似度计算，即以两文件的公共词汇占总词汇的比例来定义相似度。为简化问题，这里不考虑中文（因为分词太难了），只考虑长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。
输入格式:
输入首先给出正整数$N$（≤100），为文件总数。随后按以下格式给出每个文件的内容：首先给出文件正文，最后在一行中只给出一个字符#，表示文件结束。在$N$个文件内容结束之后，给出查询总数$M$（≤104），随后$M$行，每行给出一对文件编号，其间以空格分隔。这里假设文件按给出的顺序从1到$N$编号。
输出格式:
针对每一条查询，在一行中输出两文件的相似度，即两文件的公共词汇量占两文件总词汇量的百分比，精确到小数点后1位。注意这里的一个“单词”只包括仅由英文字母组成的、长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。单词间以任何非英文字母隔开。另外，大小写不同的同一单词被认为是相同的单词，例如“You”和“you”是同一个单词。
输入样例:
1
2
3
4
5
6
7
8
9
10
11
| 3
Aaa Bbb Ccc
#
Bbb Ccc Ddd
#
Aaa2 ccc Eee
is at Ddd@Fff
#
2
1 2
1 3
|
输出样例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<iostream>
#include<string>
#include<set>
using namespace std;
set<string> sets[100];
int main() {
int N;
scanf("%d", &N);
getchar();
for(int i = 0; i < N; i++) {
string str = "";
while(true) {
char c = getchar();
if(c == '#') {
break;
} else if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
if(c >= 'a' && c <= 'z') {
c = c - 'a' + 'A';
}
str += c;
} else {
if(str.length() >= 3) {
if(str.length() > 10){
str = str.substr(0, 10);
}
sets[i].insert(str);
}
str = "";
}
}
}
int M;
scanf("%d", &M);
for(int i = 0; i < M; i++) {
int num1, num2;
scanf("%d %d", &num1, &num2);
int common = 0;
for(set<string>::iterator it = sets[num1 - 1].begin(); it != sets[num1 - 1].end(); it++){
if(sets[num2 - 1].find(*it) != sets[num2 - 1].end()){
common++;
}
}
int total = sets[num1 - 1].size() + sets[num2 - 1].size() - common;
printf("%.1f%\n", common * 100.0 / total);
}
return 0;
}
|
