uva 156 - Ananagrams

2016-01-25 · 2 min read · hash stl 字符串

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里，最后再输出。

/* ***********************************************
Author :111qqz
Created Time :2016年01月25日 星期一 14时26分38秒
File Name :code/uva/156.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=9E5+7;
 7string str;
 8int a[N];
 9map<string,int>mp;
10map<string,int>::iterator it;
11map<string,string>toori;
12struct node
13{
14    string ori;
15    string nw;
16}st[1005];

set<string>ans;
set<string>::iterator it2;

 1int main()
 2{
 3	mp.clear();
 4	ans.clear();
 5	#ifndef  ONLINE_JUDGE 
 6	freopen("code/in.txt","r",stdin);
 7  #endif
 8	ms(a,0);
 9	int cnt = 0 ;
10	while (getline(cin,str))
11	{
12	    if (str=="#") break;
13	    int p = str.find(' ');
14	    string tmp;
15	    int len;
16	    int num;
17	    while (p!=-1)
18	    {
19	        tmp = str.substr(0,p);
20	//	cout<<"tmp:"<<tmp<<endl;
21	//	if (tmp=="") continue;
22		cnt++;
23		st[cnt].ori = tmp;

	        len = tmp.length();
	        num = 0;

 1		for ( int i = 0 ; i < len ; i ++)
 2		{
 3		    tmp[i]=tolower(tmp[i]);
 4		    int val = tmp[i]-'a'+1;  //a..z对应1..26
 5		    num +=val*val;
 6		}
 7	//	cout<<"tmp:"<<tmp<<endl;
 8		st[cnt].nw = tmp;
 9		toori[st[cnt].nw]=st[cnt].ori;
10		mp[tmp] = num;
11		a[num]++;
12		str.erase(0,p+1);
13		p = str.find(' ');
14	    }
15	    //cout<<"rstr:"<<str<<endl;
16	    tmp=str.substr(0);
17	    cnt++;
18	    st[cnt].ori=tmp;
19	     len = tmp.length();
20	     num = 0 ;
21	    for ( int i = 0  ; i < len ; i++)
22	    {
23		tmp[i]=tolower(tmp[i]);
24		int val = tmp[i]-'a'+1;
25		num +=val *val;
26	    }
27	  //  cout<<"tmp:"<<tmp<<endl;
28	    st[cnt].nw = tmp;
29	    toori[st[cnt].nw]=st[cnt].ori;
30	    mp[tmp]=num;
31	    a[num]++;
32	}
33//	cout<<"a[drIed]:"<<a[mp["dried"]]<<endl;	
34	for ( it=mp.begin() ;it!=mp.end(); it ++)
35	{
36	    int tmp = it->sec;
37	  //  cout<<"a[tmp]:"<<a[tmp]<<endl;
38	    if (a[tmp]==1)
39	    {
40		//	cout<<toori[it->fst]<<endl;
41//		cout<<it->fst<<" "<<it->sec<<" "<<toori[it->fst]<<endl;
42		ans.insert(toori[it->fst]);
43	    }
44	}
45	for ( it2=ans.begin() ; it2!=ans.end();it2++)
46	{
47	    cout<<*it2<<endl;
48	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}