Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28448

Re: Masowe wyszukiwanie anagramów

Show all headers | View raw

On 04.04.2016 17:35, Borneq wrote:
> W dniu 04.04.2016 o 17:20, Borneq pisze:
>> Jak najszybciej wyszukać anagramy? Mam słownik 100-200 tyś słów, i
>> kolejne słowa próbuję.
>> Może tak, że słownik przestawię w postaci pary - słowa
>> posortowanego,słowa?
>> np.
>> abcino,bocian
>> ?

Całkowicie wysatrczy.

> Tylko jak to sortować?,

funckją sort? ;-)


> sortowanie kubełkowe? czy to sortowanie nie
> stwarza problemów, gdy jakaś litera się powtarza,

Nie.

> Kubełków mogło by byc
> mało dla ASCII, ale trzeba by dużej liczby dla Unicodu

Hmm, ciekawostka, patrząc na tabelkę utf-8 traktując
wyrazy jak ciagi bajtów i sortując te bajty nie spowodujesz
niezamierzonej kolizji;-) żadne "ęąń" nie okaże się tym samym ciągiem
co "ółś"


Albo czegoś nie mówisz, albo przekombinowujesz:


#include <vector>
#include <string>
#include <iostream>
#include <algorithm>



using namespace std;


int main()
{

     vector <pair<string, string > > S;
     string str,strs;

     while ( cin>>str )
     {
         strs=str;
         sort(strs.begin(),strs.end());

         S.emplace_back( strs,str );
     }

     sort(S.begin(),S.end());

     for (auto it = S.begin(); it!=S.end();)
     {
         auto itend = next(it);
         while (itend!=S.end() && itend->first == it->first) ++itend;
         if (distance(it, itend)>1)
         {
             cout<<"-- "<<distance(it, itend)<<endl;
             while (it!=itend)
                 cout<<(it++)->second<<endl;

         }
         else it++;
     }

     return 0;
}

Dłużej piszę posta niż pisałem ten kod,
http://sjp.pl/slownik/growy/
2.7 mln słow, 38MB,
time ./untitled <slowa.txt >bla.txt
real	0m5.638s

Nie jest poprawny dla unikodu, ale dzięki uwadze powyżej - działa ;-)

Rekordzista
-- 13
akrom
arkom
kamor
karmo
karom
komar
makro
marko
mokra
morka
okarm
rakom
ramko


pzdr
bartekltg

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 17:20 +0200
  Re: Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 17:35 +0200
    Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-04 08:52 -0700
      Re: Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 18:21 +0200
        Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-04 12:57 -0700
          Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-04 13:05 -0700
            Re: Masowe wyszukiwanie anagramów slawek <fake@fakeemail.com> - 2016-04-05 00:17 +0200
    Re: Masowe wyszukiwanie anagramów bartekltg <bartekltg@gmail.com> - 2016-04-05 01:54 +0200
      Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-05 05:32 -0700
        Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-05 06:28 -0700
  Re: Masowe wyszukiwanie anagramów Kviat <kviat@NIE_DLA_SPAMUneostrada.pl> - 2016-04-04 18:16 +0200
    Re: Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 18:25 +0200
      Re: Masowe wyszukiwanie anagramów Kviat <kviat@NIE_DLA_SPAMUneostrada.pl> - 2016-04-04 18:49 +0200
  Re: Masowe wyszukiwanie anagramów szemrany <szemrany@offline.off> - 2016-04-04 19:07 +0200

csiph-web