資料結(jié)構(gòu)與演算法-資料下載頁
2025-07-21 17:24本頁面
【正文】 b Case 1: 長(zhǎng)此以往 Case 2: 節(jié)外生枝 Case 3: 若無其事 84 「前人種樹後人涼」的哲學(xué) 85 ? 每次千辛萬苦找到 vertical movement的目的時(shí) , 把這個(gè) movement的起點(diǎn)與終點(diǎn)用一個(gè) link記錄下來 . ? 下回遇到這個(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: 若無其事 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: 若無其事 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: 若無其事 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 89 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 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 90 ? Going up to a closest internal node (whose suffix link must be available). Suppose this upward traversal passes through t characters. ? Following the suffix link that starts from this internal node. t [i, j] 91 ? Going down by matching the tcharacter substring S[i, i + t – 1] of S. t [i, j] 92 ? Na239。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