Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Zadaniepoleganaznalezieniuklasabstrakcjirelacjirównoważnościtras,co
odpowiadaklasomabstrakcjirelacjirównoważnościcyklicznejichreprezentacji.
Najprostszyalgorytmsprawdzający,czydwasłowasącyklicznierównoważ-
ne,działawczasieO(d2),gdziedtomaksymalnadługośćobusłów.Możemy
wyznaczyćpodziałnaklasyabstrakcji,sprawdzając,czykażdaparatrasjest
cyklicznierównoważna.DajetorozwiązaniedziałającewczasieO(wh+n2d2).
marcinandrychowicz/ryby
40
Poprawieniezłożoności
Szybszerozwiązaniamożnauzyskać,stosującefektywniejszesposobyspraw-
dzaniarównoważnościcyklicznej.Nietrudnojestudowodnić,żesłowaviwsą
równoważnecykliczniewtedyitylkowtedy,gdysąrównejdługościorazvjest
podsłowemww.Używającdowolnegoliniowegoalgorytmuwyszukiwania
wzorcawtekście(np.algorytmuKnutha-Morrisa-Pratta),możemysprawdzić,
czydwasłowasąrównoważnecyklicznie,wczasieliniowym.Prowadzitodo
rozwiązaniaozłożonościO(wh+n2d).
Możnajednakzastosowaćinnepodejście.Zamiastsprawdzać,czykażda
parareprezentacjijestrównoważnacyklicznie,możemysprowadzićkażdą
reprezentacjędopewnejszczególnejpostaci,którąnazwiemyreprezentacją
kanoniczną.Będzieniąmaksymalnyleksykograficznierównoważnikcykliczny
(mlrc)reprezentacji,czylitakiesłoworównoważnecykliczniereprezentacji
trasy,którejestnajwiększewporządkuleksykograficznym(słownikowym).
Wewspomnianymprzykładziereprezentacjakanonicznadla4s,8s,9n,5nto
9n,5n,4s,8s.Wartozauważyć,żeproblemwyznaczeniamlrcmożnałatwo
zredukowaćdowyznaczaniamaksymalnegoleksykograficzniesufiksusłowa.
Nietrudnoudowodnić,żemaksymalnysufikssłowavv#,gdzie#jestnowym
symbolemmniejszymodwszystkichwystępującychwv,zaczynasięnapozycji
wskazującejpoczątekrównoważnikacyklicznegov,któryjestmaksymalny.Do
wyznaczaniamaksymalnegoleksykograficzniesufiksumożemyzastosować
algorytmDuvala,którydziaławczasieliniowym.
Dwietrasysąwówczasrównoważne,jeślimająidentycznereprezentacje
kanoniczne.Możemywięcwyznaczyćdlakażdejtrasyjejreprezentacjękano-
niczną,anastępnieposortowaćwszystkiereprezentacjekanoniczne.Proste
przejściepoposortowanejtablicypozwalawyznaczyćpodziałnaklasyabs-
trakcji.RozwiązanietakiedziaławczasieO(wh+ndlogn),jeślizastosujemy
sortowanieliniowo-logarytmiczne.ZłożonośćmożnapoprawićdoO(wh+nd),
czyliliniowejwzględemwielkościwejścia,stosującsortowaniekubełkowe
lubsortująchaszezamiastcałychreprezentacji(wtymdrugimprzypadkudo
złożonościdochodziskładniknlogn).
