Sunday, 13 May 2012

UVa 156 Ananagrams Solution

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>

using namespace std;
int main()
{
int  i,j,h;
vector<string>nt;
vector<string>ff;
vector<string>b;
map<string,int>a;
string s,r;
int c[100000],d[100000];
bool g;
while(cin>>s)
    {
    if(s=="#") break;
    r=s;
    for(i=0;i<s.length();i++)
        {
        if(s[i]>=65 && s[i]<=90) s[i]+=32;
        }
    nt.push_back(r);
    ff.push_back(s);
    }
for(i=0;i<ff.size();i++)
    {
    memset(c,0,sizeof(c));
    for(j=0;j<ff[i].length();j++)
        c[ff[i][j]]++;
    for(j=0;j<ff.size();j++)
        {
        memset(d,0,sizeof(d));
        if(i!=j)    {
                    for(h=0;h<ff[j].length();h++)
                        d[ff[j][h]]++;
                    g=true;
                    for(h=97;h<=122;h++)
                        {
                        if(c[h]!=d[h]) {
                                       g=false;
                                       break;
                                       }
                        }
                    if(g==true) {
                                a[ff[i]]=1;
                                break;
                                }
                    }
        }
    if(a[ff[i]]!=1) b.push_back(nt[i]);
    }
sort(b.begin(),b.end());
for(i=0;i<b.size();i++)
    cout<<b[i]<<endl;
return 0;
}

No comments:

Post a Comment