hihocoder 196

Posted on

hihocoder 196

逆序单词

描述

在英文中有很多逆序的单词，比如dog和god，evil和live等等。

现在给出一份包含N个单词的单词表，其中每个单词只出现一次，请你找出其中有多少对逆序单词。

输入

第1行：1个整数，N，表示单词数量。2≤N≤50,000。

第2..N+1行：每行1个单词，只包含小写字母，每个单词长度不超过16个字母。保证每个单词只出现一次，且不会出现回文单词（即一个单词倒序还是它自己，比如eye）。

输出

第1行：1个整数，表示单词表中逆序单词的对数。

样例输入

1
2
3
4
5
6
7
6
dog
live
hiho
evil
coder
god

样例输出

1
2

分析

采用set对已经读入的词进行维护，后面在set中查询。

Code

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
#include <iostream>
#include <set>
#include <string>

using namespace std;

int main() {
  int n;
  cin >> n;
  set<string> doc;
  int count = 0;
  for (int i = 0; i < n; ++i) {
    string word;
    cin >> word;
    string rever(word.rbegin(), word.rend());
    // Check word is in word set
    if (doc.find(rever) != doc.end()) {
      count++;
    } else {
      doc.insert(word);
      doc.insert(rever);
    }
  }
  cout << count << endl;
  return 0;
}