資料結(jié)構(gòu)與演算法(存儲(chǔ)版)
【正文】 n 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…… 以「若無(wú)其事」的態(tài)度處理「若無(wú)其事」的狀況 …… 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: 長(zhǎng)此以往 Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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 (斷頭指標(biāo) ) 79 Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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 The challenges: How do we derive the position of the current growing point? ? Vertically (case 2) ? Horizontally (case 3) ? Q: Which one is easier? 80 ? Moving from iteration k – 1 to iteration k. ? The growing point does not move! ? This is the easier case. Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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 81 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: 若無(wú)其事 82 ? Moving from Step i to Step i+1 in the same iteration. ? The growing point moves dramatically. ? This is the tougher case. Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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 83 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: 若無(wú)其事 84 「前人種樹(shù)後人涼」的哲學(xué) 85 ? 每次千辛萬(wàn)苦找到 vertical movement的目的時(shí) , 把這個(gè) movement的起點(diǎn)與終點(diǎn)用一個(gè) link記錄下來(lái) . ? 下回遇到這個(gè)起點(diǎn)時(shí) , 就可以直接走到終點(diǎn)去 ,不用再重新找一次 . ? 這些 link就叫做 suffix link (斷頭指標(biāo) ). 86 ? 終點(diǎn)所對(duì)應(yīng)的字串 ,是起點(diǎn)所對(duì)應(yīng)之字串的「斷頭字串」 (second suffix) Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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 87 ? 每個(gè)「斷頭指標(biāo)」的起點(diǎn)一定是個(gè) internal node, ? 不會(huì)葉子 ? 不會(huì)是某個(gè) suffix tree edge的中間 ? Why? Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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 88 ? 每個(gè) internal node一定是某個(gè)「斷頭指標(biāo)」的起點(diǎn) ? Why? Case 2: 節(jié)外生枝 Case 3: 若無(wú)其事 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
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1