> > Potreboval bych dobrej a hodne rychlej algoritmus ktery porovna dva > Jde o problém výpočtu Levenshteinovy vzdálenosti
Tedy - abych se neukvapil - nemusí to být jediné možné řešení, ale Levenshteinův algoritmus mne napadl jako první a podle popisu problému jsem usoudil, že by Vás mohl zajímat. Není ani moc dlouhý a patří do rodiny algoritmů dynamického programování, takže se moc neukecává a maká ;-). Jinak pokud by vadilo to dvourozměrné pole, tak to by mělo jít (vzhledem ke způsobu výpočtu buňky na pozici [i,j]) eliminovat tím, že by si algoritmus pamatoval pouze aktuální a předchozí řádek, pak by byla paměťová složitost O(2*min(retezec1.length(),retezec2.length())), časová zůstává O(retezec1.length()*retezec2.length()). Tomáš Záluský > > > > -----Original Message----- > > From: [EMAIL PROTECTED] > > [mailto:[EMAIL PROTECTED] On Behalf Of Stanislav Ošmera > > Sent: Friday, April 21, 2006 2:04 PM > > To: [email protected] > > Subject: algoritmus na rozdil stringu > > > > > > Ahoj, > > stringy a vyhodi mi cislo jak hodne jsou rozdilny. > > Kdyz jsou stejny tak 0, kdyz jsou si hodne podobny tak maly > > cislo....atd. > > Treba "ceska pojistovna as." a "ceska pojistovna" jsou si hodne > > podobny. Rozdil muze byt kdekoliv ve stringu takze nelze > pocitat kolik > > pozic je stejnych. Podobny stringy jsou i ty s nejakym preklepem > > "ceska pojisotonva as." > > Nedari se mi nic vhodneho nalezt ani vymyslet a kdyz neco tak to ma > > exponencialni slozitost a je to pomaly. > > Jo jde mi o obecnej algoritmus takze java v tom nehraje roli. > > Diky za pomoc. > > > > -- > > Stanislav Ošmera > > Work: +44 (0)2075 980 348 > > Cell: +44 (0)7914 635 412 > > private email: [EMAIL PROTECTED] > > work email: [EMAIL PROTECTED] > > Skype: sosmera ICQ:149634231 > > > > > >
