E-是不是复读机

题目描述：

在复读纪元2140年，复读机（们）已经放弃了如下所示的低级复读方式：
“哟，小伙汁，想不到你也是个复读机”
“哟，小伙汁，想不到你也是个复读机”
而是进化出了一种新的复读技巧：语义复读，即能复读出字面上高度相似的句子（单词顺序不一定一样）。譬如，在发生以下对话时，我们可以认为，参与对话的两人中存在复读机：
“I am not a repeater”
“I am not a repeater too”
现在我就来教你如何辨认复读机.

1. 提取出所有的单词，并统计每一句中的词频。
   2.通过余弦相似度算法进行相似度分析。
   
   我们知道，在二维向量中，假设a向量是（x1, y1），b向量是(x2, y2)，那么可以将余弦定理改写成下面的形式：
   
   将我们之前提取出的词频看成2个n维向量，可得到（1,1,1,1,1,0）和（1,1,1,1,1,1）两个向量，进行余弦计算，可得到
   
   我们认为其相似度为0.912，当相似度不小于90%时，我们就认为对话的两人中，存在复读机。

输入描述

输入包括两行由数字（0-9）、英文字符（a-z、A-Z）和空格组成的字符串。其中单词之间通过空格分隔且不区分大小写，即我们认为“At”、“at”、“AT”、“aT”为同一个单词。每个字符串总长度不超过2000.

输出描述:

在一行中输出结果，如果存在复读机，则输出“Yes”，否则输出“No”，不包含双引号。

示例1

输入

I am not a reapter
I am not a reapter too

输出

Yes

示例2

输入

Excuse me Can you tell me how much the shirt is
Yes it is nine fifteen

输出

No

思路解析：

知识点复习：substr
/*
string s = “0123456789”;
string sub1 = s.substr(5);一个数字：表示从下标为5开始一直到结尾：
sub1 = “56789”
string sub2 = s.substr(5, 3);从下标为5开始截取长度为3位：
sub2 = “567”
*/
样例中两句话要分别记录每个单词出现的次数，所以可以想到用两个map<string,int>容器去储存单词的次数，并且用set集合（不重复且自动排序的容器）去储存出现过的单词。
最后不用输入原句，所以可以将两句话全部转为大写或小写形式，便于在map映射和set集合中单词的处理。
这道题精髓的地方应该是如何在一串字符串中用substr切割每个单词。

需要使用string中的find函数去找空格。
当字符串不为空时，找到第一个空格的下标p，然后用一个新命名的string s变量暂时储存空格前的内容，也就是字符串头到空格下标p之间的内容，用substr（0，p）操作截取一个单词并用set集合中的insert插入到容器，这个string变量的map映射值也将相应加1，再循环以上操作，直到字符串剩下最后一个单词时，再单独特判：s != “” && s != " "

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
  string s1, s2, s;
  getline(cin, s1);
  getline(cin, s2);
  set<string> st;
  map<string, int> mp1, mp2;
  int i; 
  for (i = 0; i < s1.length(); i++) {
    if (s1[i] >= 'A' && s1[i] <= 'Z') s1[i] = tolower(s1[i]);
  }
  for (i = 0; i < s2.length(); i++) {
    if (s2[i] >= 'A' && s2[i] <= 'Z') s2[i] = tolower(s2[i]);
  }
  int p = s1.find(" ");
  while (p != string::npos) {
    s = s1.substr(0, p);
    st.insert(s);
    s1 = s1.substr(p+1);
    mp1[s] += 1;
    p = s1.find(" ");
  }
  if (s1 != "" && s1 != " ") {
    st.insert(s1);
    mp1[s1] += 1;
  }
  p = s2.find(" ");
  while (p != string::npos) {
    s = s2.substr(0, p);
    st.insert(s);
    s2 = s2.substr(p+1);
    mp2[s] += 1;
    p = s2.find(" ");
  }
  if (s2 != "" && s2 != " ") {
    st.insert(s2);
    mp2[s2] += 1;
  }
  int up = 0, down1=0, down2 = 0;
  for (set<string>::iterator it = st.begin(); it != st.end(); it++) {
    up += mp1[*it]*mp2[*it];
    down1 += mp1[*it]*mp1[*it];
    down2 += mp2[*it]*mp2[*it];
  }
  double sum = up*1.0/(sqrt(down1)*sqrt(down2)*1.0);
  if (sum >= 0.9000)
    cout << "Yes";
  else
    cout << "No" ;
  return 0;
}