資料結(jié)構(gòu)與演算法-預(yù)覽頁(yè)
【正文】 b b a a b b a a b a a b a b b 35 S = b b a b b a a b [1,1] [2,3] [1,2][3,3] [3,3] [1,1] [2,4][3,4][3,4][2,5][3,5][3,5][2,6][3,6][3,6][3,3] [7,7] [4,7] [3,3] [7,7] [4,7] [2,3][7,7] [4,7] [7,8] 4,8][7,8] [4,8]7,8] 4,8]? Observation: ? The tree structure does not change very often, ., only O(|S|) times. 36 ? At the beginning of the kth iteration, there are exactly k “growing points”(生長(zhǎng)點(diǎn) ), all with different heights. ? The kth iteration iteratively grows k edges with label S[k] at those k growing points. 37 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b 38 ? Three cases while growing trie ? Case 1: growing an edge at a leaf. ? Case 2: growing a new branch of leaf. ? Case 3: does not change the tree structure. 39 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b Case 1: 長(zhǎng)此以往 Case 2: 節(jié)外生枝 Case 3: 若無其事 40 ? Those k steps in the kth iteration have the following pattern: ? some (at least one) Case1 steps, ? followed by some (could be zero) Case2 steps, ? followed by some (could be zero) Case3 steps. 41 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b Case 1: 長(zhǎng)此以往 Case 2: 節(jié)外生枝 Case 3: 若無其事 42 ? 在同一個(gè) iteration之中，「長(zhǎng)此以往」之前 (下 )的 step一定也是「長(zhǎng)此以往」。 for k = 2 to |S| do pute T(k) from T(k1)。vely: O(t). ? Cleverly: O(1+ d), where d is the number of internal nodes being went through during phase (2). t [i, j] 93 ? Suppose di is the d in the ith Case2step traversal. ? It suffices to show d1+d2+…+d|S| =O(|S|). Case 2: 節(jié)外生枝 Case 3: 若無其事 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b 94 ? The slack means the distance between a position P and the closest internal node above P. t [i, j] 95 ? Each case3 traversal (., horizontal movement) can only increase the value of ? by at most one. ? (It can even decrease the value of ?.) Case 2: 節(jié)外生枝 Case 3: 若無其事 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b 96 ? The ith case2 traversal (., vertical movement) decreases the value of ? by at least di. Case 2: 節(jié)外生枝 Case 3: 若無其事 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b 97 ? Initial ? = O(1). ? ? can be increased by one for at most |S| times (because there are at most |S| horizontal movements (., case3 traversals). ? Since ? is always nonnegative, the above bound is proved. 98 S = b b a b b a a b [1,] [2,] [3,] [3,] [3,3] [7,] [4,] [3,3] [7,] [4,] [2,3] [7,] [4,] 1 [1,1] 1 2 1 1 1
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1