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