7-44 基于词频的文件相似度 (30 分)

原题：https://pintia.cn/problem-sets/15/problems/891

题意：

给出N个文件，文件里面含有各个单词，再给出若干对编号，找出每对编号文件里面共同单词，并且算出它们所占两者总单词数的比例。这个两者总单词数要注意，相同的不用加进去。例如：aaa bbb ccc 和aaa ddd ggg 这俩的总词数是5而不是6

坑点：AAA 和AAA1是共同的  [email protected] 是两个： qqqqqqq和abc  aa1a不行，必须连续起来才行，麻烦的点还是处理字符串。

用的数据结构：使用string类装进vector,并且打包起来做成结构体数组,还有map表建立关系

形如：

struct list {
	vector<string> str;
}list[101];
map<string, bool>mp[101];//下标编号就是文件编号

还有就是最后一个测试点超时的问题。一开始我用map在每次输入一对待搜索的编号，分别遍历两个文件，给单词做标记，这个办法超时了。看了这位大佬黑白灰的猫的提示才明白，可以做一个map数组，编号就是文件的编号，在建立字符串的时候就进行标记，到最后只要遍历一次就行了。值得注意的是必须用两者间较短的那个做遍历，要是随便取来遍历还是会超时- -

再讲讲string类

功能清空：

string str;
str.erase(str.begin(), str.end());//参数放进开头和结尾就可以清空

功能任取某段字符串：

string str="abcde12345";
string s = str.substr(0, 5);//取出从0开始的五个长度的字符串

 还有做本题的时候遇到string赋值的小问题

//错误示范,我老是和c搞混- -
string str="abcde";
string s; 
for(int i=0;i<str.size();i++)
{
   s[i]=str[i];
}

//正确示范
string str="abcde";
string s; 
for(int i=0;i<str.size();i++)
{
   s+=str[i];
}

AC代码： 

#include<string>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
struct list {
	vector<string> str;
}list[101];
map<string, bool>mp[101];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		while (s != "#")
		{
			string ss;
			int cnt = 0;
			for (int j = 0; j < s.size(); j++)//只存放字母
			{
				if (s[j] >= 'a' && s[j] <= 'z')
				{
					ss += s[j] - 32;
				}//全部小写转化为大写
				else if (s[j] >= 'A' && s[j] <= 'Z')
				{
					ss += s[j];
				}
				else
				{
					if (ss.size() >= 3 && ss.size() <= 10)
					{
						if (!mp[i][ss])
						{
							list[i].str.push_back(ss);
							mp[i][ss] = true;
						}
						ss.erase(ss.begin(), ss.end());//清空						
						continue;
					}
					else if (ss.size() >= 10)
					{
						string p = ss.substr(0, 10);//只取前十个字母
						if (!mp[i][p])//是不是有重复的
						{
							list[i].str.push_back(p);
							mp[i][p] = true;
						}
						ss.erase(ss.begin(), ss.end());//清空												
						continue;
					}
					else
					{
						ss.erase(ss.begin(), ss.end());//清空
						continue;
					}
				}
			}
			if (ss.size() >= 3)
			{
				if (ss.size() <= 10)
				{
					if (!mp[i][ss])//是否有重复的
					{
						list[i].str.push_back(ss);
						mp[i][ss] = true;
					}
				}
				else
				{
					string p = ss.substr(0, 10);
					if (!mp[i][p]) {
						list[i].str.push_back(p);
						mp[i][p] = true;
					}
				}
			}
			cin >> s;
		}
	}
	int nums;
	scanf("%d", &nums);
	for (int i = 0; i < nums; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		int cnt = list[x].str.size() + list[y].str.size(), cnt1 = 0;
		if (list[x].str.size() < list[y].str.size())//选一个相对较小的，不然最后一点超时
		{
			int len = list[x].str.size();
			for (int j = 0; j < len; j++)
			{
				if (!mp[y][list[x].str[j]])continue;
				else
				{
					cnt--;
					cnt1++;
				}
			}
		}
		else
		{
			int len = list[y].str.size();
			for (int j = 0; j < len; j++)
			{
				if (!mp[x][list[y].str[j]])continue;
				else
				{
					cnt--;
					cnt1++;
				}
			}
		}
		printf("%.1f%%\n", cnt1 * 100.0 / cnt);
	}
	return 0;
}