Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
cyclicallyequivalentworksintimeO(d2),wheredisthemaximumlengthof
bothwords.Wecancomputeabstractionclasses,checkingwhethereachpair
ofroutes’representationsarecyclicallyequivalent.Itleadstoasolutionthat
worksintimeO(wh+n2d2).
Improvingthecomplexity
Fastersolutionsmaybeobtainedusingmoreefficientalgorithmsforchecking
cyclicequivalence.Itisnotdifficulttoprovethattwowordsvandwofthesame
lengtharecyclicallyequivalentifandonlyifvisasubwordofww.Terefore,
usinganylinearpattern-matchingalgorithm(e.g.theKnuth-Morris-Pratt
algorithm)wecancheckwhethertwowordsarecyclicallyequivalentinlinear
time.ItleadstoasolutionwithtimecomplexityO(wh+n2d).
However,wecantryadifferentapproach.Insteadofcheckingcyclicequiva-
lenceforeachpairofrepresentations,wecantransformeachrepresentation
intosomeparticularform,whichwewillcallacanonicalrepresentation.Itwill
belexicographicallymaximumcyclicequivalent(lmce),i.e.acyclicequiva-
lentoftherepresentationthatisthegreatestinlexicographicalorder.Forthe
aforementionedexample,acanonicalrepresentationfor4s,8s,9n,5nis9n,
5n,4s,8s.Itisworthmentioningthatcomputinganlmcecanbereducedto
findingalexicographicallymaximumsuffixinaword.Itiseasytoprovethat
alexicographicallymaximumsuffixinawordvv#,where#isanewsymbol
lessthanalloccurringinv,startsonapositionindicatingthebeginningofthe
lmceofv.Telexicographicallymaximumsuffixinawordcanbefoundusing
Duval’salgorithm,whichworksinlineartime.
Tentworoutesareequivalentifandonlyiftheircanonicalrepresentations
areequal.Wecancomputeacanonicalrepresentationforeachrouteandthen
sortalltherepresentations.Asimplescanthroughthecreatedarrayallows
ustocomputetheabstractionclasses.Tatkindofsolutionworksintime
O(wh+ndlogn)ifalinear-logarithmicsortingalgorithmisapplied.Itcanbe
improvedtoO(wh+nd)żthatis,linearwiththeinputsizeżbyusingbucket
sortingorsortinghashesinsteadofthewholerepresentations(inthelattercase
thecomplexityincreasesbynlogn).
marcinandrychowicz/fishes
42
Outlineofaproofoftheroutes’homotopytheorem
Tissectionisdedicatedtothefollowingtheorem’soutlineofaproof:
Teorem.Tworoutesareequivalentifandonlyiftheyarehomotopic.
