《算法竞赛入门经典2ndEdition 》例题5-4 反片语(Ananagrams, Uva156)

下面这个是我第一开始的错误程序，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <sstream>
#include <cctype> 
#include <set>
#include <vector>
#include <map>

using namespace std;

vector<string> input;
set<string> dict; 
map<int, set<string>::iterator> m;

int main()
{
  freopen("New Text Document.txt","r",stdin);
  freopen("Output.txt","w",stdout);
  ios::sync_with_stdio(false);
  string str, word;
  stringstream ss;
  while(getline(cin, str))
  {
    if(str == "#") break;

    stringstream ss(str);
    while(ss>>word) 
    { 
      input.push_back(word);
      for(int i = 0; i < word.size(); i++) 
        word[i] = tolower(word[i]);
      sort(word.begin(), word.end()); 
      dict.insert(word);
      m[input.size()-1] = dict.find(word);
    } 
  }
  for(set<string>::iterator it = dict.begin(); it != dict.end(); it++) cout<<*it<<endl;
  return 0;
} 

后来我看了下书上代码定义的stl容器后，看到了标程定义map的方式，稍加改动，AC了。
这个是我的程序，我用的是set，这样在最后就不必排序了。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <sstream>
using namespace std;

set<string> words;
string s, word;
map<string, int> maps;

string transform(string);

int main()
{
  freopen("New Text Document.txt","r",stdin);
  freopen("Output.txt","w",stdout);
  ios::sync_with_stdio(false);
  while(getline(cin, s))
  {
    if(s[0] == '#') break;
    stringstream ss(s);
    while(ss>>word) 
    {
      words.insert(word);
      word = transform(word);
      //transform(word);
      if(!maps.count(word))
      {
        maps[word] = 0;
      } 
      maps[word]++;
    } 
  }
  for(set<string>::iterator it = words.begin(); it != words.end(); it++)
  {
    if(maps[transform(*it)] == 1) cout<<*it<<endl;
  }

  return 0;
} 

string transform(string word)
{
  for(int i = 0; i < word.size(); i++)
    word[i] = tolower(word[i]);
  sort(word.begin(), word.end());
  return word;
}

这个是刘汝佳标程。

// UVa156 Ananagrams
// Rujia Liu
// 题意：输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排得到输入文本中的另外一个单词
// 算法：把每个单词“标准化”，即全部转化为小写字母然后排序，然后放到map中进行统计
#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

map<string,int> cnt;
vector<string> words;

// 将单词s进行“标准化”
string repr(string s) {
  string ans = s;
  for(int i = 0; i < ans.length(); i++)
    ans[i] = tolower(ans[i]);
  sort(ans.begin(), ans.end());
  return ans;
}

int main() {
  int n = 0;
  string s;
  while(cin >> s) {
    if(s[0] == '#') break;
    words.push_back(s);
    string r = repr(s);
    if(!cnt.count(r)) cnt[r] = 0;
    cnt[r]++;
  }
  vector<string> ans;
  for(int i = 0; i < words.size(); i++)
    if(cnt[repr(words[i])] == 1) ans.push_back(words[i]);
  sort(ans.begin(), ans.end());
  for(int i = 0; i < ans.size(); i++)
    cout << ans[i] << "\n";
  return 0;
}