Note: This article is available in Chinese only. 本文暂无英文版本。
View original
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92 题意：给出一段文字，包含若干个单词，以’#‘结束。按照字典序输出所有的ananagrams。所谓ananagram，是指经过任意的重排后，不能得到这段文字中的另一个单词（不区分大小写） 思路：首先是字符串的读入…可以整行读入然后用空格分隔单词。由于补区分大小写，所以要都转化成小写…但是输出的时候要输出原始，所以还记得保留一份。而且要能够通过新的找到原始的（我用了一个toori的map<string,string>来实现） 然后最关键的部分是如何判断两个单词经过重排是否能一样…
我的做法是构造一个hash函数…一个单词的hash值等于对应字母的顺序的平方和…效果还不错？
单词和hash值一一对应…最大也就9E5,可以存的下。然后统计每个hash值出现的次数。对于那些只出现一次的，就是我们要的答案。
还要注意的是输出要按照原始单词的字典序，而不是都变成小写以后的字典序。
所以找到之后可以先找到对应的原始单词存到set里，最后再输出。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年01月25日 星期一 14时26分38秒
4File Name :code/uva/156.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=9E5+7;
34string str;
35int a[N];
36map<string,int>mp;
37map<string,int>::iterator it;
38map<string,string>toori;
39struct node
40{
41 string ori;
42 string nw;
43}st[1005];
44
45set<string>ans;
46set<string>::iterator it2;
47
48int main()
49{
50 mp.clear();
51 ans.clear();
52 #ifndef ONLINE_JUDGE
53 freopen("code/in.txt","r",stdin);
54 #endif
55 ms(a,0);
56 int cnt = 0 ;
57 while (getline(cin,str))
58 {
59 if (str=="#") break;
60 int p = str.find(' ');
61 string tmp;
62 int len;
63 int num;
64 while (p!=-1)
65 {
66 tmp = str.substr(0,p);
67 // cout<<"tmp:"<<tmp<<endl;
68 // if (tmp=="") continue;
69 cnt++;
70 st[cnt].ori = tmp;
71
72 len = tmp.length();
73 num = 0;
74
75 for ( int i = 0 ; i < len ; i ++)
76 {
77 tmp[i]=tolower(tmp[i]);
78 int val = tmp[i]-'a'+1; //a..z对应1..26
79 num +=val*val;
80 }
81 // cout<<"tmp:"<<tmp<<endl;
82 st[cnt].nw = tmp;
83 toori[st[cnt].nw]=st[cnt].ori;
84 mp[tmp] = num;
85 a[num]++;
86 str.erase(0,p+1);
87 p = str.find(' ');
88 }
89 //cout<<"rstr:"<<str<<endl;
90 tmp=str.substr(0);
91 cnt++;
92 st[cnt].ori=tmp;
93 len = tmp.length();
94 num = 0 ;
95 for ( int i = 0 ; i < len ; i++)
96 {
97 tmp[i]=tolower(tmp[i]);
98 int val = tmp[i]-'a'+1;
99 num +=val *val;
100 }
101 // cout<<"tmp:"<<tmp<<endl;
102 st[cnt].nw = tmp;
103 toori[st[cnt].nw]=st[cnt].ori;
104 mp[tmp]=num;
105 a[num]++;
106 }
107// cout<<"a[drIed]:"<<a[mp["dried"]]<<endl;
108 for ( it=mp.begin() ;it!=mp.end(); it ++)
109 {
110 int tmp = it->sec;
111 // cout<<"a[tmp]:"<<a[tmp]<<endl;
112 if (a[tmp]==1)
113 {
114 // cout<<toori[it->fst]<<endl;
115// cout<<it->fst<<" "<<it->sec<<" "<<toori[it->fst]<<endl;
116 ans.insert(toori[it->fst]);
117 }
118 }
119 for ( it2=ans.begin() ; it2!=ans.end();it2++)
120 {
121 cout<<*it2<<endl;
122 }
123
124
125
126 #ifndef ONLINE_JUDGE
127 fclose(stdin);
128 #endif
129 return 0;
130}