karlangadas

Ananagrams

Dec 10th, 2016
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <cstring>
  4. #include <set>
  5. using namespace std;
  6. string arr[100000];
  7. int ana[100000];
  8. int nwords;
  9. set<string>resp;
  10. char minuscula(char c){
  11.    
  12.     if (c>='A' && c<='Z'){
  13.         return (c+'a'-'A');
  14.         }
  15.     return c;
  16. }
  17. int veces(char c,int n){
  18.     int nveces=0;
  19.     for (int i=0;i<arr[n].size();i++)
  20.         if (minuscula(arr[n][i])==c)
  21.             nveces++;
  22.     return nveces;
  23. }
  24. int SonAnagramas(int a,int b){
  25.     //cout<<"Veamos si "<<arr[a]<<" y "<<arr[b]<<" son anagramas"<<endl;
  26.     //cout<<arr[a].size()<<" "<<arr[b].size()<<endl;
  27.     if (arr[a].size()!=arr[b].size())
  28.         return 0;
  29.     for (int i=0;i<arr[a].size();i++){
  30.         char c=minuscula(arr[a][i]);
  31.         //cout<<c<<" aparece en "<<arr[a]<<" "<<veces(c,a)<<"veces y aparece en "<<arr[b]<<" "<<veces(c,b)<<" veces."<<endl;
  32.         if (veces(c,a)!=veces(c,b)){
  33.             //cout<<"No son anagramas"<<endl;
  34.             return 0;}
  35.     }
  36.     return 1;
  37. }  
  38. void VerificaAnanagrama(int n){
  39.     int anag=1;
  40.     for (int i=(n+1);i<nwords;i++){
  41.         if (ana[i]==1){
  42.             //cout<<arr[i]<<" es ananagrama, comparemos"<<endl;
  43.             if (SonAnagramas(n,i)){
  44.                 //cout<<arr[n]<<" y "<<arr[i]<<" son anagramas"<<endl;
  45.                 anag=0;
  46.                 ana[n]=0;ana[i]=0;
  47.             }
  48.         }
  49.     }
  50.     if (anag==1)
  51.         resp.insert(arr[n]);
  52. }
  53. int main() {
  54.     string s;
  55.    
  56.     for (int i=0;i<100000;i++) ana[i]=1;
  57.     nwords=0;
  58.     while (cin>>s && s!="#"){
  59.             arr[nwords]=s;
  60.             nwords++;
  61.     }
  62.     for (int i=0;i<nwords;i++){
  63.         if (ana[i]==1){
  64.             //cout<<"se va a verificar: "<<arr[i]<<endl;
  65.             VerificaAnanagrama(i);}
  66.     }
  67.    
  68.     for (set<string>::iterator it=resp.begin();it!=resp.end();it++)
  69.         cout<<*(it)<<endl;
  70.    
  71.    
  72. }
Advertisement
Add Comment
Please, Sign In to add comment