我的GIS/CS学习笔记：https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 > 还有不少数据结构和算法相关的笔记以及pta题解哦x
思路
倒排索引的结构如下： “关键词1”：“文档1”的ID，“文档2”的ID，…………。 “关键词2”：带有此关键词的文档ID列表。 从词的关键字，去找文档。
题目
实现一种简单原始的文件相似度计算，即以两文件的公共词汇占总词汇的比例来定义相似度。为简化问题，这里不考虑中文（因为分词太难了），只考虑长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。
输入格式:
输入首先给出正整数N（≤100），为文件总数。随后按以下格式给出每个文件的内容：首先给出文件正文，最后在一行中只给出一个字符#，表示文件结束。在N个文件内容结束之后，给出查询总数M（≤104），随后M行，每行给出一对文件编号，其间以空格分隔。这里假设文件按给出的顺序从1到N编号。
输出格式:
针对每一条查询，在一行中输出两文件的相似度，即两文件的公共词汇量占两文件总词汇量的百分比，精确到小数点后1位。注意这里的一个“单词”只包括仅由英文字母组成的、长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。单词间以任何非英文字母隔开。另外，大小写不同的同一单词被认为是相同的单词，例如“You”和“you”是同一个单词。
输入样例:
3 Aaa Bbb Ccc # Bbb Ccc Ddd # Aaa2 ccc Eee is at Ddd@Fff # 2 1 2 1 3
输出样例:
代码语言：javascript复制50.0% 33.3%
#include <iostream>
#include<map>
#include<list>
#include<ctype.h>
#include<string>
#include<cctype>
#include<algorithm>
//倒排索引；
//(inverted index)
using namespace std;
//link[i][i]: words in a file;
//link[j][j]: public words;
int link[105][105];
//index:
map<string, list<int> > words;
int main(int argc, const char * argv[]) {
int n, i, j, k;
cin >> n;
string line, aword;
map<string, list<int> >::iterator word;
//input
for (i = 1; i <= n; i) {
int count = 0;
getline(cin, line);
while (line[0] != '#') {
j = 0;
while (j < line.length()) {
k = 0;
aword.clear();
//create word;
while (k < 10 && isalpha(line[j])) {
aword = line[j];
j;
k;
}
while (isalpha(line[j]))
j;
//deal with a word;
if (aword.length()>=3) {
transform(aword.begin(), aword.end(), aword.begin(), ::tolower);
word = words.find(aword);
if (word==words.end()||word->second.back() != i) {
//if not in this file but exist:
if (word != words.end()) {
list<int>::iterator f;
f = word->second.begin();
//update public words;
while (f != word->second.end()) {
link[i][*f] ;
link[*f][i] ;
f;
}
}
//if not exist:
words[aword].push_back(i);
count;
}
}
else
j;
}
getline(cin, line);
}
link[i][i]= count;
}
//output:
int m, f1, f2;
cin >> m;
double per;
for (i = 0; i < m; i) {
cin >> f1 >> f2;
per = 1.0*link[f1][f2] / (link[f1][f1] link[f2][f2] - link[f1][f2])*100;
printf("%.1f%%n", per);
}
return 0;
}
