7-44 基于词频的文件相似度（30 分）

ゝ一世哀愁。 2022-03-09 09:54 192阅读 0赞

7-44 基于词频的文件相似度 （30 分）

实现一种简单原始的文件相似度计算，即以两文件的公共词汇占总词汇的比例来定义相似度。为简化问题，这里不考虑中文（因为分词太难了），只考虑长度不小于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

### 输出样例: ###

50.0%
    33.3%

输入用stringsteam很方便，可以分割空格。

但是一段中也有可能包含非字母的，要断开，比如Ddd\#Fff其实是“ddd"和“fff”

用暴力的方法对比的话最后一个点会超时

所以用一重循环，count一下x在y里出现的次数即可。

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    #include<string>
    #include<map>
    #include<stack>
    #include<vector>
    #include<algorithm>
    #include<sstream>
    #include<set>
    #include<iostream>
    using namespace std;
    #define inf 0x3f3f3f
    int main()
    {
    	int n,m,x,y,i,j,l;
    	cin>>n;cin.get();
    	map<string,int> a[105];
    	string s;	
    	for(j=1;j<=n;j++)
    	{
    		while(getline(cin,s))
    		{
    			if(s=="#")break;
    			stringstream ss(s);
    			while(ss>>s)
    			{
    				string op="";
    				i=0;
    				while(i<s.size())
    				{
    					if(s[i]>='A'&&s[i]<='Z')
    					op+=s[i]+32;
    					else if(s[i]>='a'&&s[i]<='z')
    					op+=s[i];
    					else 
    					{
    						if(op.size()<3);
    						else if(op.size()>10)
    						{
    							op=op.substr(0,10);
    							a[j][op]++;
    						}
    						else a[j][op]++;
    						op.clear();
    					}
    					i++;
    				}	
    				if(op.size()<3)continue;
    				else if(op.size()>10)
    				{
    					op=op.substr(0,10);
    					a[j][op]++;
    				}
    				else a[j][op]++;				
    			}
    		}
    	}
    	scanf("%d",&m);
    	while(m--)
    	{
    		scanf("%d%d",&x,&y);
    		int sum=0;
    		for(map<string,int>::iterator it=a[x].begin();it!=a[x].end();it++)
    		{
    			if(a[y].count(it->first))sum++;
    		}
    		if((int)a[x].size()+(int)a[y].size()-sum==0)printf("0.0%%\n");
    		else printf("%.1f%%\n",100.*sum/((int)a[x].size()+(int)a[y].size()-sum));
    	}
    }