資料結構與演算法(文件)
【正文】 his” iteration, if a step is “若無其事 ”, then all its following steps are also “若無其事 ”. 56 ? 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. This is about the status within the same iteration 57 葉子的宿命 ––– 一日為葉子 , 終身為葉子 58 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: 長此以往 Case 2: 節(jié)外生枝 Case 3: 若無其事 59 ? Only O(|S|) Case2 steps throughout the execution. ? Why? 60 ? 葉子生長點之所對應的 edge label ? 斷頭指標 ? … 61 Case1 Step 62 ? Always occurs at a leaf (growing point). ? At the beginning of iteration k, the path above a leaf has label [?, k–1]. ? Each Case1 step in iteration k simply changes the label [?, k–1] to [?, k]. [?, k–1] [?, k] 63 ? Use [?, ] to label the path above each leaf. ? Thus, no need to do anything for each case1 step. [?, ] 64 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 21 1 1 65 ? We can simply ignore all Case1 steps. ? Recall that the number of Case2 steps is at most |S|. ? Q: Is this good enough? Case 1: 長此以往 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 66 Case2 Steps: 節(jié)外生枝 67 ? Always occurs at a growing point that is not a leaf, which is not necessarily an internal node. ? When the growing point is an internal node … ? Label = [k, ], where k is the current iteration index. [k, ] 68 ? When the growing point is not an internal node … [k, ] t [i, j] [i+t, j] [i, i+t1] 69 Case3 Steps: 若無其事 70 ? Always occurs at a growing point that is not a leaf, which is not necessarily an internal node. ? When the new position of the growing point is an internal node … t [i, j] 0 71 ? When the new position of the growing point is not an internal node … t [i, j] t + 1 72 ? Give a sequence S such that the number of Case3 steps throughout the process of growing its suffix trie (or suffix tree) is W(|S|2). 73 Completely ignore them…… 以「若無其事」的態(tài)度處理「若無其事」的狀況 …… 74 t [i, j] 0 t [i, j] t + 1 75 1. For correctly maintaining the position of each growing point. (Why?) 2. For correctly running Case2 steps. (By what?) [k, ] t [i, j] [i+t, j] [i, i+t1] 76 Saving the book keeping efforts in all Case3 steps … 77 Case 1: 長此以往 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 78 ? Just keep one current growing point throughout the execution. ? Deriving the new position of the current growing point from its previous position (with the helpusing suffix links (斷頭指標 ) 79 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
公司管理相關推薦
鄂ICP備17016276號-1