将sequence最后一个数字后面加上一个符号.ppt

HOMEWORK3,Problem1:Growthesuffixtreefor“baabcbbabc”.DrawtheintermediatetreewithgrowingpointandsuffixlinksforeachstepofUkkonensalgorithm,aswedidintheclass.,HOMEWORK3,1234567890S=baabcbbabc,1,-,HOMEWORK3,1234567890S=baabcbbabc,1,-,2,-,HOMEWORK3,1234567890S=baabcbbabc,1,-,2,-,1,HOMEWORK3,1234567890S=baabcbbabc,1,-,3,-,4,-,2,2,HOMEWORK3,1234567890S=baabcbbabc,1,-,3,-,4,-,2,2,1,HOMEWORK3,1234567890S=baabcbbabc,2,-,3,-,4,-,2,2,5,-,1,1,HOMEWORK3,1234567890S=baabcbbabc,2,-,3,-,4,-,2,2,5,-,1,1,5,-,HOMEWORK3,1234567890S=baabcbbabc,2,-,3,-,4,-,2,2,5,-,1,1,5,-,HOMEWORK3,1234567890S=baabcbbabc,2,-,3,-,4,-,2,2,5,-,5,-,7,-,1,1,HOMEWORK3,1234567890S=baabcbbabc,2,-,3,-,4,-,2,2,5,-,1,1,5,-,7,-,HOMEWORK3,1234567890S=baabcbbabc,2,-,3,-,4,-,2,2,5,-,1,1,5,-,7,-,1,HOMEWORK3,1234567890S=baabcbbabc,3,-,3,-,4,-,2,2,5,-,1,1,5,-,7,-,9,-,2,2,HOMEWORK3,1234567890S=baabcbbabc,3,-,3,-,4,-,2,2,5,-,1,1,5,-,7,-,9,-,2,2,1,HOMEWORK3,1234567890S=baabcbbabc,3,-,3,-,4,-,5,-,1,1,5,-,7,-,9,-,2,2,2,2,2,HOMEWORK3,Problem2:ShowhowtoconstructaminimatreeforanysequenceSofnumbersinO(|S|)time.,HOMEWORK3,Input：asequenceofnumbersa1、a2、anOutput：aminimatreeTAlgorithm：一、將sequence最後一個數字後面加上一個符號，令其為負無限大；令T為一個LIFO的stack，儲存minimatree；二、將sequence第一個數字存到T中，三、fori:=2ton+1doinputaipopaminimatreefromstackTcompareaiwiththerootRofminimatreeifRpop出來minimatree的樹根，則ai與該樹根都會被push進去；若aiR則，ai會被push到stack中，之後當有數字aj當時stackpop出來的樹根R時，stack才會一直pop數字出來與aj比較，直到有個樹根比aj小，此時被pop出來的樹根會被combine起來，存到aj的左子樹，之後便不會在被拿出來比較了，故比較次數最多不超過2n次，所以時間複雜度為O(n)。TAscomments:Inanotheropinion,sinceeachcharactermustperformamulti-popoperationandbepushintothestackeithercombiningwithexistingminimatreesorforminganewminimatreewithasinglenode,thenumberofoveralloperationsforthestackafterscanningthewholestringis2n.Besides,eachcombinationrequiresconstanttime.Therefore,wegainthetimecomplexityforthealgorithmisO(n).T